6.9. 使用二叉堆的优先队列¶
6.9. Priority Queues with Binary Heaps
在前面的部分中，你了解了先进先出（FIFO）数据结构——队列。一种重要的队列变体称为优先队列。优先队列的操作方式类似于队列，你可以通过从前面移除项目来出队。然而，在优先队列中，队列内项目的逻辑顺序是由它们的优先级决定的。最高优先级的项目位于队列的前面，而最低优先级的项目位于队列的后面。因此，当你向优先队列中入队一个项目时，新项目可能会移动到队列的前面。我们将在下一章中看到，优先队列是一些图算法中非常有用的数据结构。
你可能会想到几种简单的方法来使用排序函数和列表来实现优先队列。然而，将项目插入到列表中的时间复杂度是 \(O(n)\)，而对列表进行排序的时间复杂度是 \(O(n \log{n})\)。我们可以做得更好。经典的优先队列实现方式是使用一种数据结构——二叉堆。二叉堆允许我们在 \(O(\log{n})\) 时间内完成入队和出队操作。
二叉堆之所以有趣，是因为当我们绘制堆的结构图时，它看起来很像一棵树，但在实现时我们只使用一个列表作为内部表示。二叉堆有两个常见的变体：最小堆（min heap），其中最小的键值总是位于前面；以及最大堆（max heap），其中最大的键值总是位于前面。在这一节中，我们将实现最小堆。最大堆的实现留作练习。
In earlier sections you learned about the first in, first out data structure called a queue. One important variation of a queue is called a priority queue. A priority queue acts like a queue in that you dequeue an item by removing it from the front. However, in a priority queue the logical order of items inside a queue is determined by their priority. The highest priority items are at the front of the queue and the lowest priority items are at the back. Thus when you enqueue an item on a priority queue, the new item may move all the way to the front. We will see that the priority queue is a useful data structure for some of the graph algorithms we will study in the next chapter.
You can probably think of a couple of easy ways to implement a priority queue using sorting functions and lists. However, inserting into a list is \(O(n)\) and sorting a list is \(O(n \log{n})\). We can do better. The classic way to implement a priority queue is using a data structure called a binary heap. A binary heap will allow us both to enqueue and dequeue items in \(O(\log{n})\).
The binary heap is interesting to study because when we diagram the heap it looks a lot like a tree, but when we implement it we use only a single list as an internal representation. The binary heap has two common variations: the min heap, in which the smallest key value is always at the front, and the max heap, in which the largest key value is always at the front. In this section we will implement the min heap. We leave a max heap implementation as an exercise.
创建日期: 2024年9月9日