優先級隊列的二進制堆的優點？

看來我錯過了一件非常簡單的事情：比較一下優先級隊列和二級堆的優點，比如說快速排序的數組值？在這兩種情況下，我們將值保存在一個數組中，插入爲O（logN），在兩種情況下，delete-max均爲O（1）。在這兩種情況下，給定元素陣列的初始構造都是O（NlogN），但鏈接http://en.wikipedia.org/wiki/Heap_%28data_structure%29表示爲二進制堆構造提供了更快的Floyd算法。但是在排隊的情況下，這些元素可能會一個接一個地被接收，所以這個優點就消失了。另外，合併似乎對二進制堆更好。
那麼除了合併之外，還有什麼理由更喜歡BH？也許我的假設是錯誤的，BP只用於學習目的。我檢查了C++文檔，他們提到了「堆」，但它當然不一定意味着二進制堆。
有點類似的問題：When is it a bad idea to use a heap for a Priority Queue?
請解釋downvotes，如果有的話 - 我真的想明白這一點。優先級隊列的二進制堆的優點？

來源

2014-01-19 TT_

實際上，這裏有很多關於SO的問題都提到了二叉樹作爲PQ的實現。 –

另一個比較堆和二叉樹：http://stackoverflow.com/questions/15637446/why-heap-is-better-than-binary-tree-to-represent-a-priority-queue?rq=1 但是這個問題的答案在這裏沒有關係。 –

@templatetypedef對不起，我犯了一個錯誤：對於BH，delete-max是O（logN），我的意思是find-max是O（1）。我在閱讀你的答案後意識到了這一點。 –

二進制堆的主要優點是可以在初始構建它之後有效地向其添加新值。假設你想用一個有序數組來返回一個優先級隊列。如果隊列中的所有值都事先已知，則可以按照前面所述對值排序。但是當你想要爲優先隊列添加一個新值時會發生什麼？在最壞的情況下，這可能需要時間Θ（n），因爲您必須將所有數組元素向下移動以爲您剛添加的新元素留出空間。另一方面，插入到二進制堆中需要花費時間O（log n），其指數地更快。

如果你只需要出列幾個元素，那麼你會在一個有序數組上使用堆的另一個原因。正如你所提到的，對一個數組進行排序需要花費時間O（n log n），但是使用巧妙的算法可以在時間O（n）中構建一個堆。如果需要從中建立一個優先級隊列和剩餘的k個元素，其中k是未知的，則排序數組的運行時間爲O（n log n + k），二進制堆爲O（n + k log n ）。對於小k，第二種算法要快得多。

希望這有助於！

來源

2014-01-19 18:28:36 templatetypedef

謝謝！我會把Θ（n）的使用放在另一個+1上。我還有一個問題。當我問原來的問題時，我錯過了那個轉變的部分。但是可以對已排序的數組進行優化嗎？在這種情況下，只有一個連續的塊必須被移位，而不是BH的O（logN）交換。 –

如果你有一個n元素的數組，並且需要在它的中間插入一個元素，那麼即使列表已經排序，你也需要將n/2個元素移開以騰出空間。除非您從使用陣列切換到其他數據結構，否則無法避免支付這筆費用。 – templatetypedef

優先級隊列的二進制堆的優點？

回答

相關問題