優先級隊列 - 二進制堆

我想實現一個優先級隊列作爲排序數組支持最小二進制堆。我試圖讓update_key函數在對數時間運行，但要做到這一點，我必須知道該數組中項目的位置。無論如何不使用地圖來做到這一點？如果是這樣，怎麼樣？謝謝優先級隊列 - 二進制堆

2012-04-15 Richard

什麼是update_key函數？ – DRVic 2012-04-15 02:06:22

函數更新元素的鍵，因爲二進制堆包含一個鍵，元素對 – Richard 2012-04-15 02:54:56

您的查找鍵功能應該在log（n）時間內運行。您的更新（更改密鑰）應該是固定的時間。您的刪除功能應該在log（n）時間運行。您的插入功能應該是log（n）時間。

如果這些假設是真的試試這個： 1）在你的堆找到你的項目（IE：二進制搜索，因爲它是一個排序數組）。 2）更新你的密鑰（你只是改變一個值，不變的時間） 3）從堆日誌（n）中刪除項目以重新組織。
4）將你的項目插入堆日誌（n）。所以，你會有log（n）+ 1 + log（n）+ log（n），它減少到log（n）。

注意：這是分期付款，因爲如果你不得不重新分配你的數組等等......這會增加開銷。但是你不應該經常這樣做。

來源

2012-04-15 03:45:54

我不認爲他意味着排序數組。典型的二進制堆實現將元素保存在一個數組中，但只有heap屬性需要爲true。保持所有元素排序並仍然具有O（log（n））複雜度來插入和刪除元素是不可能的我想。 – 2012-04-15 06:33:16

這很有道理。假設一個人使用真正的堆結構，堆的根節點只需要比兩個孩子更好（就排序而言），那麼每個孩子可以被認爲是另一個堆的根，並且這是遞歸地應用的）。我不知道爲什麼昨晚我沒有想到這一點。感謝您的澄清。 – 2012-04-15 13:51:15

這是數組支持的堆的權衡：你獲得了優秀的內存使用（良好的局部性和最小的開銷），但是你失去了元素的軌跡。要解決這個問題，你必須添加一些開銷。

一個解決方案就是這樣。該堆包含C*類型的對象。 C是int成員heap_index的類，它是堆陣列中對象的索引。無論何時移動堆陣列中的元素，都必須更新其heap_index以將其設置爲新索引。因此需要一段時間才能找到元素（通過heap_index）和log（n）時間將其冒泡到正確的位置，因此Update_key（以及去除任意元素）是log（n）時間。

來源

2012-04-15 05:10:08

如果你真的想要改變任意元素的鍵，堆不是數據結構的最佳選擇。什麼它給你的是組合：

緊湊表示（沒有指針，只是一個數組和隱式索引方案）
對數插入，再平衡
對數去除最小（最大）元素。
O（1）訪問最小（最大）元素的值。 -

1.的一個好處是缺少指針意味着您可以大大減少對malloc/free（new/delete）的調用次數。的地圖（在標準庫作爲一個平衡二叉樹表示）爲您提供了中間兩個的這些，對任意鍵添加在

對數find()。

因此，儘管你可以附加其他數據結構的堆，存儲在堆棧指針，然後通過指針進行比較運算解引用，你會很快發現自己與時間的複雜性和公正空間首先使用map。

來源

2012-04-16 11:29:10 DRVic

優先級隊列 - 二進制堆

回答

相關問題