替換和刪除堆中的操作

Question

我正在解決一個需要使用堆數據結構解決的問題。雖然操作將由insert和extract-min控制，但是會出現需要替換項​​目的鍵（增加或減少）或刪除項目，鍵的情況。由於heapq模塊不提供這些操作，並且在堆中搜索物品將是O(n)，因此只需使用字典進行簿記，然後僅用它來查找物品的位置，刪除或替換物品並調用heapify來恢復堆屬性 - 總體上所有這些操作將在O(logn)中運行。 問題是，我無法實現這樣的字典，但。

h, bkp = [], {} 
heappush(h, (5, 'a')) 
bkp['a'] = # index of 'a' in heap 
heappush(h, (7, 'b')) 
bkp['b'] = # index of 'b' in heap 
heappush(h, (1, 'c')) 
bkp['c'] = # index of 'c' in heap 

# deleting 'a' 
h[bkp['a']], h[-1] = h[-1], h[bkp['a']] 
h.pop() 
heapify(h) 

#update indices in bkp 

問題 - 如何找到在堆和刪除或推操作之後新插入的索引，我該如何重新計算指數堆中現有的項目？

Answer 1

有幾種方法可以做到這一點。

一種選擇是通過在對象本身內存儲每個對象的位置來使你的堆侵入。這樣，只要你想查找一個對象的位置，你可以在O（1）中通過查看對象內的位置字段來實現。

您還可以存儲輔助散列表或BST以及將堆中的每個值映射到堆中的位置的堆。這與第一種方法類似，但具有額外的間接層。

希望這會有所幫助！