使用堆作为优先级队列

使用堆数据结构的主要方法之一是创建优先队列。正如我们在 第 4 章 "构建堆和队列" 中所看到的，优先级队列是一种特殊的队列，其先进先出行为取决于元素的优先级，而不是项目添加到队列的方式。我们已经了解了使用关联列表和 SPL 的实现方法。现在，我们将探索使用堆，尤其是最大堆实现优先级队列。

现在，我们将使用 MaxHeap 来实现优先级队列。在这里，优先级最高的项目会首先从队列中移除。我们的实现方法与上次 MinHeap 的实现方法类似，但有一点不同。因此，左右子项的计算方法也会发生变化。这将有助于我们理解使用数组构造堆的两种方法。下面是 MaxHeap 类的实现：

让我们来看看 MaxHeap 类的实现。我们的 MaxHeap 实现与上一节中的 MinHeap 实现有一些细微差别。第一个不同点是，MaxHeap 中的数组大小为 n，而 MinHeap 中的数组大小为 n+1。这使得 MaxHeap 的插入操作从索引 0 开始，而 MinHeap 则从索引 1 开始。siftUp 功能只有在新插入项的值大于直接父项的值时，才会将该值移到顶层。此外，extractMax 方法会返回数组中位于索引 0 的第一个值，即堆中的最大值。提取最大值后，我们需要从其余项中获取最大值，并将其存储在索引 0 处。siftDown 函数还会检查左侧或右侧子节点的值是否大于父节点的值，然后我们交换值，将最大值存储在父节点处。我们将继续递归执行此操作，以确保在函数调用结束时将最大值存储在根节点中。如果我们愿意，可以将 MaxHeap 实现用作独立的堆实现。

由于我们计划使用堆来实现优先队列，因此我们将添加另一个类来扩展 MaxHeap 类，以显示优先队列的特性。让我们看看下面的代码：

在这里，我们只是对 MaxHeap 类进行了扩展，并在隐身模式下使用 insert 和 extractMax 为 enqueue 和 dequeue 操作添加了一个封装。现在，让我们使用与 MinHeap 相同的数据运行 PriorityQ 代码：

从前面的代码可以看出，我们并不是直接从数组中构造堆。我们使用优先级队列类将队列中的每个数字枚举出来。此外，dequeue 操作将从队列中获取最高优先级的项目。如果我们从命令行运行这段代码，将得到以下输出结果：

从输出结果中我们可以看到，MaxHeap 实现帮助我们在每次去队列操作中获取最大值项。这是实现优先队列的方法之一。如果我们愿意，也可以一次性对整个堆进行排序，然后将排序后的数组用作优先队列。为此，我们可以实现一个被称为堆排序的排序功能。它是计算机编程中最有效、最常用的排序机制之一。我们将在下一节对此进行探讨。