在二进制堆中删除

Question

我只是想学习二进制堆,并对在二进制堆中执行删除操作有疑问.我已经读过我们可以从二进制堆中删除一个元素,我们需要重新封装它.

但在以下链接中,它表示不可用:

http://en.wikibooks.org/wiki/Data_Structures/Tradeoffs

                Binary Search  AVL Tree   Binary Heap (min)  Binomial Queue (min)

Find            O(log n)       O(log n)   unavailable         unavailable
Delete element  O(log n        O(log n)   unavailable         unavailable

我对此感到困惑.

提前感谢所有澄清.

Answer 1

二叉堆和其他优先级队列结构通常不支持一般的“删除元素”操作；您需要一个额外的数据结构来跟踪堆中每个元素的索引，例如哈希表。如果有的话，您可以实现常规删除操作：

• find-element，哈希表的预期时间为 O(1)
• 将密钥减少到小于最小值，O(lg n ) 时间
• 删除分钟并更新哈希表，O(lg n ) 组合预期时间。