二进制堆是否支持reduce-key操作？

Question

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

因此,由于Web上缺少实现,是否可以在二进制堆中执行reduce-key操作？

Answer 1

我想出来了:

• 为了在O(logn)中执行减少键,我们必须事先知道相应元素的位置.哈希映射和良好的哈希函数可以保证O(1)摊销时间.每次修改后,我们都必须更新哈希映射,它需要O(logn).
• 在确定元素的位置之后,我们将元素向上移动,以防它具有比其父元素更高的优先级(以类似于插入的方式),或者如果它的优先级低于其子元素,则向下移动元素(以类似于删除)并更新哈希映射中修改后的元素的位置.