引言
优先队列是图算法中最核心的辅助数据结构之一。二叉堆以其简洁的实现和稳定的O(log n)操作复杂度成为首选，但在实际应用中，尤其是涉及大量decrease-key操作的场景（如Dijkstra、Prim算法），二叉堆并非最优选择。
配对堆（Pairing Heap）由Fredman、Sedgewick、Sleator和Tarjan于1986年提出，是一种自适应的堆结构。它在实际运行中往往比斐波那契堆更快（尽管理论复杂度尚不完全确定），同时实现远比斐波那契堆简单。本文将用Java实现配对堆，并展示其如何加速Dijkstra算法。
核心原理
配对堆是一种多叉堆，通过”配对合并”（pairing merge）操作维护堆性质。其核心操作极其简单：
- merge（合并）：将两个堆的根节点中较小者作为新根，较大者成为其第一个子节点。
- insert（插入）：将新节点与原堆合并。
- delete-min（删除最小值）：移除根节点后，将其所有子节点通过两两配对合并的方式重新组织。
- decrease-key（减小键值）：如果新键值仍满足堆序，只需更新值；否则剪断该节点，将其与原堆合并。
删除最小值时的两两配对合并策略：
1. 从左到右，相邻两个子树两两合并（第一轮配对）。
2. 从右到左，将配对结果依次合并（第二轮累积合并）。
Java完整实现
import java.util.*;
/**
* 配对堆（Pairing Heap）实现
* 一种自适应优先队列，decrease-key操作实际效率极高
* @param <T> 元素类型
*/
public class PairingHeap<T extends Comparable<T>> {
// 堆节点
static class Node<T> {
T key; // 键值
Node<T> child; // 第一个子节点
Node<T> sibling; // 右兄弟节点
Node<T> parent; // 父节点（用于decrease-key）
Node(T key) {
this.key = key;
}
}
private Node<T> root; // 根节点
private int size; // 节点数量
public PairingHeap() {
this.root = null;
this.size = 0;
}
/**
* 判断堆是否为空
*/
public boolean isEmpty() {
return root == null;
}
/**
* 获取堆中元素数量
*/
public int size() {
return size;
}
/**
* 查看最小元素（不移除）
*/
public T findMin() {
if (root == null) {
throw new NoSuchElementException("堆为空");
}
return root.key;
}
/**
* 合并两个配对堆，返回新堆的根
* 核心操作：较小的根成为新根
*/
private Node<T> merge(Node<T> h1, Node<T> h2) {
if (h1 == null) return h2;
if (h2 == null) return h1;
// h1的根更小，h2成为h1的第一个子节点
if (h1.key.compareTo(h2.key) <= 0) {
h2.sibling = h1.child;
h1.child = h2;
h2.parent = h1;
return h1;
} else {
// h2的根更小
h1.sibling = h2.child;
h2.child = h1;
h1.parent = h2;
return h2;
}
}
/**
* 插入新元素
*/
public Node<T> insert(T key) {
Node<T> newNode = new Node<>(key);
root = merge(root, newNode);
size++;
return newNode;
}
/**
* 删除并返回最小元素
* 核心：将根的所有子节点通过两两配对合并重新组织
*/
public T deleteMin() {
if (root == null) {
throw new NoSuchElementException("堆为空");
}
T minKey = root.key;
Node<T> firstChild = root.child;
// 两两配对合并（从左到右）
Node<T> newRoot = mergePairs(firstChild);
root = newRoot;
size--;
return minKey;
}
/**
* 两两配对合并子节点列表
* 第一轮：从左到右相邻两个合并
* 第二轮：从右到左依次累积合并
*/
private Node<T> mergePairs(Node<T> firstChild) {
if (firstChild == null) return null;
if (firstChild.sibling == null) return firstChild;
// 第一轮：从左到右两两合并
Node<T> pairs = null; // 配对结果链表的头
Node<T> pairsTail = null;
Node<T> curr = firstChild;
while (curr != null && curr.sibling != null) {
Node<T> next = curr.sibling;
Node<T> afterNext = next.sibling;
// 断开连接
curr.sibling = null;
next.sibling = null;
// 合并curr和next
Node<T> merged = merge(curr, next);
// 加入配对结果链表
if (pairs == null) {
pairs = merged;
} else {
pairsTail.sibling = merged;
}
pairsTail = merged;
curr = afterNext;
}
// 处理奇数个的情况，最后一个单独加入
if (curr != null) {
if (pairs == null) {
pairs = curr;
} else {
pairsTail.sibling = curr;
}
pairsTail = curr;
}
// 第二轮：从右到左累积合并
// 找到尾部
if (pairs == null) return null;
// 将链表反转以便从右到左处理，或者递归处理
// 这里采用递归方式：将链表分为第一个和剩余部分
return mergePairsRecursive(pairs);
}
/**
* 递归地从右到左合并配对结果
*/
private Node<T> mergePairsRecursive(Node<T> node) {
if (node == null || node.sibling == null) {
return node;
}
// 先合并后面的
Node<T> rest = mergePairsRecursive(node.sibling);
node.sibling = null;
return merge(node, rest);
}
/**
* 减小指定节点的键值
* 这是配对堆最大的优势所在
*/
public void decreaseKey(Node<T> node, T newKey) {
if (newKey.compareTo(node.key) >= 0) {
throw new IllegalArgumentException("新键值必须小于当前键值");
}
node.key = newKey;
// 如果节点是根，直接完成
if (node == root) {
return;
}
// 将节点从其父节点中剪断
// 找到node在父节点的子节点列表中的位置
Node<T> parent = node.parent;
if (parent != null) {
if (parent.child == node) {
parent.child = node.sibling;
} else {
// 在兄弟链表中查找
Node<T> prev = parent.child;
while (prev != null && prev.sibling != node) {
prev = prev.sibling;
}
if (prev != null) {
prev.sibling = node.sibling;
}
}
}
node.sibling = null;
node.parent = null;
// 将剪断的子树与原堆合并
root = merge(root, node);
}
/**
* 中序遍历打印（用于调试）
*/
public void printHeap() {
System.out.println("堆大小: " + size);
if (root != null) {
System.out.print("堆结构: ");
printNode(root, 0);
System.out.println();
}
}
private void printNode(Node<T> node, int depth) {
if (node == null) return;
System.out.println(" ".repeat(depth) + node.key);
printNode(node.child, depth + 1);
printNode(node.sibling, depth);
}
// ==================== Dijkstra加速应用 ====================
static class Edge {
int to, weight;
Edge(int to, int weight) {
this.to = to;
this.weight = weight;
}
}
/**
* 使用配对堆优化的Dijkstra算法
*/
public static int[] dijkstraWithPairingHeap(List<Edge>[] graph, int source) {
int n = graph.length;
int[] dist = new int[n];
Arrays.fill(dist, Integer.MAX_VALUE);
dist[source] = 0;
// 使用配对堆作为优先队列
PairingHeap<int[]> heap = new PairingHeap<>();
// 记录每个顶点在堆中的节点，用于decrease-key
@SuppressWarnings("unchecked")
Node<int[]>[] nodes = new Node[n];
// 初始化：源点距离为0
nodes[source] = heap.insert(new int[]{0, source});
while (!heap.isEmpty()) {
int[] curr = heap.deleteMin();
int d = curr[0], u = curr[1];
// 跳过过期条目
if (d > dist[u]) continue;
for (Edge e : graph[u]) {
if (dist[u] + e.weight < dist[e.to]) {
dist[e.to] = dist[u] + e.weight;
// 如果该顶点已在堆中，执行decrease-key
// 否则插入新节点
if (nodes[e.to] != null) {
heap.decreaseKey(nodes[e.to], new int[]{dist[e.to], e.to});
} else {
nodes[e.to] = heap.insert(new int[]{dist[e.to], e.to});
}
}
}
}
return dist;
}
/**
* 使用Java标准PriorityQueue的Dijkstra（对比基准）
*/
public static int[] dijkstraWithPriorityQueue(List<Edge>[] graph, int source) {
int n = graph.length;
int[] dist = new int[n];
Arrays.fill(dist, Integer.MAX_VALUE);
dist[source] = 0;
PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[0]));
pq.offer(new int[]{0, source});
while (!pq.isEmpty()) {
int[] curr = pq.poll();
int d = curr[0], u = curr[1];
if (d > dist[u]) continue;
for (Edge e : graph[u]) {
if (dist[u] + e.weight < dist[e.to]) {
dist[e.to] = dist[u] + e.weight;
pq.offer(new int[]{dist[e.to], e.to});
}
}
}
return dist;
}
public static void main(String[] args) {
System.out.println("=== 配对堆基础测试 ===");
PairingHeap<Integer> heap = new PairingHeap<>();
// 插入测试
int[] values = {5, 3, 8, 1, 9, 2, 7};
@SuppressWarnings("unchecked")
Node<Integer>[] nodes = new Node[values.length];
for (int i = 0; i < values.length; i++) {
nodes[i] = heap.insert(values[i]);
System.out.println("插入 " + values[i] + ", 最小值: " + heap.findMin());
}
// decrease-key测试
System.out.println("\n将 9 减小到 0");
heap.decreaseKey(nodes[4], 0); // 将9减小到0
System.out.println("decrease-key后最小值: " + heap.findMin());
// 删除最小值测试
System.out.println("\n依次删除最小值:");
while (!heap.isEmpty()) {
System.out.print(heap.deleteMin() + " ");
}
System.out.println();
System.out.println("\n=== Dijkstra性能对比测试 ===");
int n = 1000;
int m = 5000;
Random rand = new Random(42);
@SuppressWarnings("unchecked")
List<Edge>[] graph = new ArrayList[n];
for (int i = 0; i < n; i++) graph[i] = new ArrayList<>();
for (int i = 0; i < m; i++) {
int u = rand.nextInt(n);
int v = rand.nextInt(n);
int w = rand.nextInt(100) + 1;
graph[u].add(new Edge(v, w));
graph[v].add(new Edge(u, w)); // 无向图
}
long start1 = System.currentTimeMillis();
int[] dist1 = dijkstraWithPairingHeap(graph, 0);
long time1 = System.currentTimeMillis() - start1;
long start2 = System.currentTimeMillis();
int[] dist2 = dijkstraWithPriorityQueue(graph, 0);
long time2 = System.currentTimeMillis() - start2;
// 验证结果一致
boolean match = Arrays.equals(dist1, dist2);
System.out.println("结果一致性: " + match);
System.out.println("配对堆Dijkstra耗时: " + time1 + "ms");
System.out.println("优先队列Dijkstra耗时: " + time2 + "ms");
}
}
复杂度分析
配对堆的理论复杂度至今仍是开放问题，但已证明和实际观测的复杂度如下：
| 操作 | 均摊复杂度 | 实际表现 |
|---|---|---|
| insert | O(1) | 极快，仅需一次合并 |
| find-min | O(1) | 直接读取根节点 |
| delete-min | O(log n) | 两两配对合并非常高效 |
| decrease-key | O(1) ~ O(log n) | 实际中接近O(1)，远快于二叉堆 |
| merge | O(1) | 单次比较和指针调整 |
decrease-key的优势：在Dijkstra算法中，标准PriorityQueue不支持decrease-key，需要插入重复节点（造成”过期条目”），堆大小可能达到O(E)。配对堆通过decrease-key将堆大小控制在O(V)，对于稠密图优势尤为明显。
应用场景
- Dijkstra/Prim加速：大量decrease-key操作的图算法场景。
- 任务调度器：支持动态调整任务优先级的调度系统。
- 实时系统：实现简单、常数因子小的优先队列。
总结
配对堆以其极简的实现和出色的实际性能，成为优先队列领域的一颗明珠。它没有斐波那契堆复杂的级联剪切（cascading cut）机制，却能在实际运行中匹敌甚至超越后者。对于涉及大量decrease-key操作的算法（如Dijkstra、Prim），配对堆是理想的优先队列实现选择。
