二進制堆優先級隊列的位置索引？

假設我有一個優先級隊列，其中有N個優先級隊列，其中N的數量是幾千個，使用一個優先隊列來實現，隊列的優先級爲binary heap。我瞭解EXTRACT-MIN和INSERT原語（請參閱Cormen, Leiserson, Rivest，它使用-MAX而不是-MIN）。二進制堆優先級隊列的位置索引？

但是DELETE和DECREASE-KEY都似乎要求優先級隊列能夠在給定項目本身的堆中找到項目的索引（或者，該索引需要由優先級隊列的使用者給出，但這似乎是抽象違規）......看起來像是一個疏忽。有沒有辦法有效地做到這一點，而不必在堆頂部添加散列表？

來源

2009-08-17 Jason S

「但是，DELETE和DECREASE-KEY似乎都要求優先級隊列能夠在給定項本身的堆中找到項目的索引。」 - 從代碼中可以清楚的看出，至少有一些方法使用堆中的索引而不是項目的優先級。很明顯，我是HEAP-INCREASE-KEY中的一個索引：

HEAP-INCREASE-KEY(A, i, key) 
    if key < A[i] 
     then error 'new key is smaller than current key" 
    A[i] <-- key 
    ...

所以，如果這是API，請使用它。

來源

2009-08-17 23:21:35 hughdbrown

它是*堆的API，而不是優先級隊列。 –

此外，只要您從堆中插入或提取項目，索引不再保證有效，因此瞭解某個時間點項目的索引並不一定能幫助您知道索引項目在另一個時間點。 –

對，我認爲這裏的重點在於，對於優先級隊列的實現，您可以使用一個二進制堆，API的HEAP-INCREASE-KEY（A，i，key）需要一個索引（i），但可以允許優先隊列的接口採用任意密鑰。您可以自由地將優先級隊列封裝到密鑰 - >索引映射的詳細信息中。如果你需要你的PQ-INCREASE-KEY（A，舊的，新的）在O（log n）中工作，那麼你最好有一個O（log n）或更好的鍵來查找索引，以保持最新。這可能是一個哈希表或其他快速查找結構。

所以，要回答你的問題：我認爲這是不可避免的，數據結構將增加一些方法。

來源

2009-09-24 09:06:08 bockmabe

我修改了我的節點類以添加一個heapIndex成員。這是由堆維護，因爲節點在插入，刪除，減少等過程中交換。

這打破封裝（我的節點現在綁在堆上），但它運行速度很快，這在我的情況下更重要。

來源

2010-02-08 05:21:38

一種方法是將堆分成一側的組件和另一側的組織。

如需全部功能，您需要建立兩種關係： a）給定堆位置（例如Root），找到坐在那裏的元素。 b）給定一個元素，找到它的堆位置。

第二個方法很簡單：在每次將元素移動到堆中時更新值「location」（很可能是基於數組的堆中的索引）。

第一個也很簡單：不是存儲元素，而是保存一堆指向元素（或數組元素）的指針。現在，給定一個位置（例如Root），可以通過解引用它（或訪問矢量）來找到坐在那裏的元素。

來源