一个优先队列是一种数据结构，它允许我们插入带有优先级的元素，并检索出优先级最高的那个元素。
我们可以使用数组或堆来实现优先队列。基于数组和基于堆的优先队列实现各有其优缺点。数组通常更容易实现，但因为插入和删除元素需要移动数组中的元素，所以速度可能会较慢。堆的效率更高，但实现起来可能更复杂。您也可以参考堆与有序数组之间的区别，以了解这两者之间的一般性比较。
基于堆的实现优先队列
这涉及到创建一个二叉堆数据结构，并在插入和移除元素时维护堆的性质。在二叉堆中，优先级最高的元素始终是堆的根节点。要插入一个元素，我们可以将其添加到堆的末尾，然后执行必要的堆操作（例如将元素与其父节点交换）以恢复堆的性质。要获取优先级最高的元素，只需返回堆的根节点即可。
要使用堆来实现优先队列，我们可以遵循以下步骤：
- 创建一个堆数据结构（最大堆或最小堆）
- 要将元素插入优先队列，使用堆的插入函数将元素添加到堆中。堆将自动重新排列元素以维护堆的性质。
- 要移除优先级最高的元素（在最大堆中）或优先级最低的元素（在最小堆中），请使用堆的移除函数。这将移除树的根节点并重新排列剩余元素以维护堆的性质。
示例 1：
C++
CODEBLOCK_45ab75bb
Java
import java.util.ArrayList;
import java.util.List;
class PriorityQueue {
static class Node {
String task;
int priority;
Node(String task, int priority) {
this.task = task;
this.priority = priority;
}
}
List heap = new ArrayList();
// Adds a task to the priority queue
public void insert(String task, int priority) {
heap.add(new Node(task, priority));
int idx = heap.size() – 1;
while (idx != 0) {
int parentIdx = (idx – 1) / 2;
if (heap.get(parentIdx).priority < heap.get(idx).priority) {
swap(parentIdx, idx);
idx = parentIdx;
} else {
break;
}
}
}
// Extracts the task with the highest priority
public Node extractMax() {
Node maxNode = heap.get(0);
heap.set(0, heap.get(heap.size() – 1));
heap.remove(heap.size() – 1);
int idx = 0;
while (idx < heap.size()) {
int leftChildIdx = idx * 2 + 1;
int rightChildIdx = idx * 2 + 2;
int largerChi