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

Question

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

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

Answer 1

我发现：

• 为了在 O(logn) 中执行减少键，我们必须提前知道相应元素的位置。哈希映射和良好的哈希函数可以保证 O(1) 摊余时间。每次修改后，我们都必须更新哈希映射，这需要 O(logn)。
• 确定元素的位置后，如果元素的优先级高于其父级（与插入类似），则向上移动元素；如果元素的优先级低于其子级之一（与插入类似），则向下移动元素（与插入类似）删除）并更新哈希映射中修改的元素的位置。