为什么最大优先级队列没有DECREASE-KEY？

Question

在堆数据结构的讨论中,例如在CLRS中,最大优先级队列只需要INSERT,MAXIMUM,EXTRACT-MAX和INCREASE-KEY.但为什么它也没有DECREASE-KEY,至少它的操作也会使堆属性失效？它几乎不重要吗？

Answer 1

FWIW 我的 CLR V1 讨论了 INSERT、MIN、EXTRACT-MIN、UNION、DECREASE-KEY 和 DELETE，但我们可以通过翻转符号转换为您的版本。

我认为这个集合是由使用优先级队列的算法的要求驱动的，例如最小生成树、Dijstra 最短路径和（我怀疑）A*。例如，如果您查看有关最小生成树的章节的开头，您会看到一条注释，如果您用斐波那契堆替换二叉堆，则 Prim 的算法可以加快速度。