为什么最大优先级队列没有DECREASE-KEY？
在堆数据结构的讨论中，例如CLRS中，最大优先级队列只需要INSERT 、最大值、提取最大值和增加键。但为什么它不也有DECREASE-KEY，至少它的操作也会使堆属性失效呢？它实际上不重要吗？
In the discussion of heap data structure, for example in CLRS, the max-priority queue only needs INSERT, MAXIMUM, EXTRACT-MAX, and INCREASE-KEY. But why doesn't it also have DECREASE-KEY, at the least, its operation will also invalidate the heap property? Is it practically unimportant?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
如果您有 MAX-HEAP，则在 CLRS 第 3 版第 6.2 节“维护堆属性”中，DECREASE-KEY 将是 MAX-HEAPIFY。
If you have a MAX-HEAP, DECREASE-KEY will be MAX-HEAPIFY in section 6.2 "Maintaining the heap property" of CLRS, 3rd edition.
没有什么可以阻止您在二进制堆中实现 DECREASE-KEY。它可以在 O(log N) 内完成，而不会破坏任何不变量。
我的猜测是它不包括在内，因为它并不经常需要。
Nothing is stopping you to implement DECREASE-KEY in your binary heap. It can be done in O(log N) without breaking any invariants.
My guess is that it isn't included, because it's not needed very often.
FWIW 我的 CLR V1 讨论了 INSERT、MIN、EXTRACT-MIN、UNION、DECREASE-KEY 和 DELETE，但我们可以通过翻转符号转换为您的版本。
我认为这个集合是由使用优先级队列的算法的要求驱动的，例如最小生成树、Dijstra 最短路径和（我怀疑）A*。例如，如果您查看最小生成树章节的开头，您会看到一条注释，如果您用斐波那契堆替换二叉堆，则 Prim 的算法可以加快速度。
FWIW my CLR V1 talks about INSERT, MIN, EXTRACT-MIN, UNION, DECREASE-KEY, and DELETE, but we can convert to your version by flipping signs.
I think this set is driven by the requirements of the algorithms that use priority queues, such as minimum spanning tree, Dijstra shortest path, and (I suspect) A*. For instance, if you look at the start of the chapter on minimum spanning trees, you can see a note that Prim's algorithm can be sped up if you replace binary heaps with fibonacci heaps.