algorithm - maxheap 和在头部存储最大值的链表有什么区别？

Question

我现在正在我的算法课上学习堆，但无法理解在实践中，最大堆如何优于仅将最大值存储在头指针处的链表。

让一个节点有两个比它小的 child 有什么意义，为什么它不能像链表那样只有一个？基本上，堆能做什么而链表不能？我觉得我在这里缺少一些基本的东西。

Answer 1

两者都是 Priority queue 的实现抽象数据类型。区别在于性能——插入或移除项目需要多长时间。

您可以将优先级队列实现为简单的无序链表。每当您添加一个项目时，只需将其设为列表的新头部即可。当有人要求最大项时，您搜索列表以找到最大的一项，将其从列表中删除，然后返回。所以插入速度非常快，每次获取最大项都需要对列表进行全扫描。

您还可以维护一个排序列表。在这种情况下，插入一个项目是昂贵的，因为您必须按顺序搜索列表以找到要插入新项目的位置。但是获取最大项非常快:它位于列表的头部。

不过，假设您有一个包含一百万个项目的列表。在第一种情况下，查找最大项目需要您搜索整个列表。在第二种情况下，插入一个项目平均需要搜索列表的一半。

另一方面，最大堆是一种妥协。它的插入速度不如无序列表快，删除速度也不如有序列表快。但它在删除时比无序列表快多，在插入时比排序列表快多。

下面我列出了这三种优先级队列的两种基本操作的渐近复杂度:

                   Insert     Delete-Max
Unordered list      O(1)        O(n)
Sorted list         O(n)        O(1)
Binary max heap     O(log n)    O(log n)

再次假设您的优先级队列中有 1,000,000 个项目。您想要添加一个项目，然后删除最大值。无序列表将需要一次快速操作来插入一个项目，并且您必须搜索 1,000,000 个项目才能找到最大值。

排序列表平均需要 500,000 次操作才能插入一个项目，但您可以非常快速地删除最大项目。

log₂(1000000) 大约是 20。最大堆最多需要 20 次操作来插入一个项目，最多需要 20 次操作来移除一个项目。

应该清楚，如果需要维护优先级队列，最大堆比链表效率高得多。

现在，如果您的数据已经排序并且您只需要按顺序遍历它们，那么您当然不需要堆。您甚至不需要链表。一个数组将是要走的路。但是当您同时进行添加和删除操作时，维护一个堆会给您带来更好的性能。

即使您正在维护一个非常小的队列——比如 10 个项目——链表和最大堆之间的性能差异也是非常明显的。如果您的应用程序的性能取决于优先级队列实现的速度，那么花时间了解堆数据结构是值得的。

有关上述内容的更详细版本，请参阅我在 Priority queues 上的博客条目和 Heaps ，以及讨论实现的后续文章。