algorithm - 为什么最小堆比最大堆更适合实现优先级队列？

Question

在我用来研究算法和数据结构的一本书中，它指出最小堆比最大堆更适合实现优先级队列。为什么会这样？

为什么使用堆来实现优先级队列是个好主意？

标签： algorithmdata-structuresheappriority-queue

Answer 1

更多算法需要最小堆，例如 Dijkstra 的。但实际上，如果您只是否定所有元素，则 min-heap 和 max-heap 是等价的。

堆是实现优先级队列的一种简单有效的方法，因为（根据堆的性质）它在您添加/删除时保持自身“排序”，因此可以快速插入和删除最小元素（如果最小堆）。这些正是优先级队列需要的操作，因此堆非常适合。