二进制堆是否支持reduce-key操作？ [英] Does a binary heap support the decrease-key operation?

问题描述

根据 http://en.wikipedia.org/wiki/Heap_%28data_structure%29#Comparison_of_theoretic_bounds_for_variants ，需要Θ（logn）（其转换为O（logn））来执行减号操作。然而，似乎没有一个包含减号键操作的二进制堆实现的站点。

According to http://en.wikipedia.org/wiki/Heap_%28data_structure%29#Comparison_of_theoretic_bounds_for_variants, it takes Θ(logn) (which translates to O(logn)) to perform the decrease-key operation. However, there seems to be no site that includes a binary heap implementation with a decrease-key operation.

因此，网络上缺少实现，是否可以在二进制堆中执行减号操作？

Given therefore the lack of implementations on the web, is it possible to perform the decrease-key operation in a binary heap?

推荐答案

我想到了：

• 为了在O（logn）中执行减号键，我们必须提前知道相应元素的位置。散列图和散列函数可以保证O（1）的摊销时间。每次修改后，我们必须更新哈希映射，这需要O（logn）。


• 确定元素的位置之后，我们将元素移动到更高的优先级如果它的优先级低于其子项之一（以类似的方式删除），并且更新哈希映射中修改后的元素的位置，则它的父（与插入相似的方式）或向下舍入）。/ / li>
  

• In order to perform a decrease-key in O(logn), we have to know the location of the corresponding element in advance. A hash map and a good hash function can guarantee O(1) amortized time. After each modification, we have to update the hash map, which takes O(logn).
• After determining the location of our element, we move our element up in case it has a greater priority than its parent (in a similar manner to insertion) or down if it has a lower priority than one of its children (in a similar manner to deletion) and update the modified elements' locations in the hash map.

这篇关于二进制堆是否支持reduce-key操作？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！