优先队列
1. 概念与基本原理
优先队列是一种特殊的队列，其中每个元素都有一个优先级。在处理元素时，具有最高优先级的元素最先被处理。与普通队列（先进先出）和栈（后进先出）不同，优先队列按元素的优先级进行处理。
2. 实现方式
无序数组实现
- 插入操作：将元素添加到数组末尾（O(1)）
- 删除最大元素：遍历找到最大元素，与最后一个元素交换后删除（O(N)）
有序数组实现
- 插入操作：找到合适位置插入，保持数组有序（O(N)）
- 删除最大元素：直接返回并删除数组末尾元素（O(1)）
链表实现
与数组实现类似，可以选择维护有序或无序链表
2.2 各种实现的性能比较
| 数据结构 | 插入元素 | 删除最大元素 |
|---|---|---|
| 有序数组 | N | 1 |
| 无序数组 | 1 | N |
| 堆 | logN | logN |
| 理想情况 | 1 | 1 |
3. 堆的定义与结构
3.1 堆有序
当一棵二叉树的每个节点都大于等于它的两个子节点时，称为堆有序。在堆有序的二叉树中，从任意节点向上，会得到一列非递减的元素；从任意节点向下，会得到一列非递增的元素。
3.2 二叉堆
二叉堆是一组能够用堆有序的完全二叉树排序的元素，并在数组中按层级顺序存储（通常不使用数组的第一个位置）。主要特点：
- 位置k的节点的父节点位于k/2处
- 位置k的节点的子节点位于2k和2k+1处
- 大小为N的完全二叉树的高度为⌊lgN⌋
3.3 表示方法
数组索引: 0 1 2 3 4 5 6 7 8 9 10
数组内容: - T S R P N O A E I H
堆表示: T
/ \
S R
/ \ / \
P N O A
/ \ /
E I H
4. 堆的基本操作
4.1 上浮操作（由下至上的堆有序化）
当某个节点的优先级上升（比如插入新元素）时，为恢复堆的有序性，需要将该节点与其父节点比较，如果其大于父节点则交换位置，直到满足堆有序要求。
private void swim(int k) {
while (k > 1 && less(k/2, k)) {
exch(k/2, k);
k = k/2;
}
}
4.2 下沉操作（由上至下的堆有序化）
当某个节点的优先级下降（比如替换为一个较小的元素）时，为恢复堆的有序性，需要将该节点与其较大的子节点比较，如果其小于子节点则交换位置，直到满足堆有序要求。
private void sink(int k) {
while (2*k <= N) {
int j = 2*k;
if (j < N && less(j, j+1)) j++;
if (!less(k, j)) break;
exch(k, j);
k = j;
}
}
5. 堆的核心操作实现
5.1 插入元素
将新元素加到数组末尾，增加堆的大小，然后让这个新元素上浮到正确位置。
public void insert(Key v) {
pq[++N] = v; // 将新元素加到数组末尾
swim(N); // 恢复堆的有序性
}
5.2 删除最大元素
从数组顶端删去最大元素，将数组的最后一个元素放到顶端，减小堆的大小，然后让这个元素下沉到正确位置。
public Key delMax() {
Key max = pq[1]; // 获取最大元素
exch(1, N--); // 将其与最后一个元素交换
pq[N+1] = null; // 防止对象游离
sink(1); // 恢复堆的有序性
return max; // 返回最大元素
}
5.3 性能分析
- 在含有N个元素的基于堆的优先队列中：
- 插入元素操作需要不超过(lgN+1)次比较
- 删除最大元素操作需要不超过2lgN次比较
6. 完整的优先队列实现
public class MaxPQ<Key extends Comparable<Key>> {
private Key[] pq; // 基于堆的完全二叉树
private int N = 0; // 存储于pq[1..N]中，pq[0]未使用
public MaxPQ(int maxN) {
pq = (Key[]) new Comparable[maxN+1];
}
public boolean isEmpty() {
return N == 0;
}
public int size() {
return N;
}
public void insert(Key v) {
pq[++N] = v;
swim(N);
}
public Key delMax() {
Key max = pq[1];
exch(1, N--);
pq[N+1] = null;
sink(1);
return max;
}
private boolean less(int i, int j) {
return pq[i].compareTo(pq[j]) < 0;
}
private void exch(int i, int j) {
Key t = pq[i]; pq[i] = pq[j]; pq[j] = t;
}
private void swim(int k) {
while (k > 1 && less(k/2, k)) {
exch(k/2, k);
k = k/2;
}
}
private void sink(int k) {
while (2*k <= N) {
int j = 2*k;
if (j < N && less(j, j+1)) j++;
if (!less(k, j)) break;
exch(k, j);
k = j;
}
}
}
7. 堆排序算法
堆排序利用堆的性质进行排序，分为两个阶段：
- 堆的构造阶段：将无序数组重新组织安排成一个堆
- 下沉排序阶段：从堆中按递减顺序取出所有元素
7.1 堆的构造
从右至左使用sink()函数构造子堆，效率高于从左至右使用swim()。
// 堆的构造
for (int k = N/2; k >= 1; k--)
sink(a, k, N);
堆的构造只需少于2N次比较以及少于N次交换。
7.2 下沉排序
重复删除最大元素并将其放入数组末尾空出的位置。
// 下沉排序
while (N > 1) {
exch(a, 1, N--);
sink(a, 1, N);
}
7.3 完整堆排序实现
public static void sort(Comparable[] a) {
int N = a.length;
// 堆的构造阶段
for (int k = N/2; k >= 1; k--)
sink(a, k, N);
// 下沉排序阶段
while (N > 1) {
exch(a, 1, N--);
sink(a, 1, N);
}
}
private static void sink(Comparable[] a, int k, int N) {
while (2*k <= N) {
int j = 2*k;
if (j < N && less(a, j, j+1)) j++;
if (!less(a, k, j)) break;
exch(a, k, j);
k = j;
}
}
private static boolean less(Comparable[] a, int i, int j) {
return a[i-1].compareTo(a[j-1]) < 0;
}
private static void exch(Comparable[] a, int i, int j) {
Comparable t = a[i-1];
a[i-1] = a[j-1];
a[j-1] = t;
}
7.4 堆排序性能分析
- 将N个元素排序：
- 堆排序需要少于(2NlgN+2N)次比较
- 以及一半次数的交换
- 空间复杂度：O(1)，原地排序
- 时间复杂度：O(N log N)，最优化利用时间和空间的排序算法
- 缺点：无法利用现代计算机的缓存机制，实际应用中可能不如快排和归并排序