data-structures - 二叉堆是否支持减键操作？

Question

根据 http://en.wikipedia.org/wiki/Heap_%28data_structure%29#Comparison_of_theoretic_bounds_for_variants ，执行减键操作需要 Θ(logn)(转换为 O(logn))。但是，似乎没有站点包含具有减少键操作的二进制堆实现。

鉴于网络上缺乏实现，是否可以在二叉堆中执行减键操作？

Answer 1

我想出了这个:

为了在 O(logn) 中执行减少键，我们必须提前知道相应元素的位置。一个哈希映射和一个好的哈希函数可以保证 O(1) 分摊时间。每次修改后，我们必须更新哈希映射，这需要 O(logn)。

在确定元素的位置后，我们将元素向上移动，以防它的优先级高于其父级(与插入的方式类似)或向下移动，如果它的优先级低于其子级之一(以类似于插入的方式)删除)并更新已修改元素在哈希图中的位置。