Question

6.8.基于二叉堆的优先队列

在前面的部分中，你了解了称为队列的先进先出数据结构。队列的一个重要变种称为优先级队列。优先级队列的作用就像一个队列，你可以通过从前面删除一个项目来出队。然而，在优先级队列中，队列中的项的逻辑顺序由它们的优先级确定。最高优先级项在队列的前面，最低优先级的项在后面。因此，当你将项排入优先级队列时，新项可能会一直移动到前面。我们将在下一章中研究一些图算法看到优先级队列是有用的数据结构。

你可能想到了几种简单的方法使用排序函数和列表实现优先级队列。然而，插入列表是 $O(n)$O(n) 并且排序列表是 $O(nlogn)$O(nlogn)。我们可以做得更好。实现优先级队列的经典方法是使用称为二叉堆的数据结构。二叉堆将允许我们在 $O(logn)$O(logn) 中排队和取出队列。

二叉堆是很有趣的研究，因为堆看起来很像一棵树，但是当我们实现它时，我们只使用一个单一的列表作为内部表示。二叉堆有两个常见的变体：最小堆（其中最小的键总是在前面）和最大堆（其中最大的键值总是在前面）。在本节中，我们将实现最小堆。我们将最大堆实现作为练习。