为什么一个最大堆没有一个减少键操作，而一个最小堆一个增加键操作？

Question

递增键或减少键的操作分别用于在最大堆或最小堆中更新密钥.

为什么一个最大堆没有一个减少键操作，而一个最小堆一个增加键操作？

谢谢。

Answer 1

这在这里之前已经讨论过了。总之，这些操作可以很容易地在O(log(n))中实现，但通常不提供，因为从纯算法的角度来看，它们几乎没有兴趣。

相反，min堆上的减键在Fibonacci中有一个现有的O(1)实现，并且有一个应用程序，例如在Dijkstra路径查找中。