索引堆及其优化详解：原理、图示与Java实现
索引堆及其优化详解：原理、图示与Java实现
引言
索引堆（Indexed Heap），也称为索引优先队列（Indexed Priority Queue），是一种扩展的堆数据结构。它在标准二进制堆的基础上，引入索引机制，允许高效地更新和删除任意元素，而不仅仅是堆顶元素。这在图算法（如Dijkstra最短路径算法）中特别有用，因为它能快速调整特定节点的优先级。 标准优先队列（如Java的PriorityQueue）不支持高效的任意元素更新，而索引堆通过额外映射解决了这个问题。
原理
索引堆的核心是结合二进制堆和索引映射：
- 二进制堆基础：元素存储在数组中，形成完全二叉树。最小堆（Min-Heap）确保父节点小于或等于子节点；最大堆（Max-Heap）则相反。操作如插入（swim上浮）和删除（sink下沉）维持堆性质，时间复杂度为O(log n)。
- 索引机制：使用两个数组实现双向映射：
pq[]：堆数组，存储索引（而非直接值），1-based indexing。qp[]：逆映射数组，qp[i] 表示索引i在pq中的位置。keys[]：存储实际键值，按索引访问。- 关键操作：
- 插入（insert）：添加键到keys[i]，更新pq和qp，然后上浮（swim）调整堆。
- 删除最小（delMin）：移除堆顶，交换末尾元素，下沉（sink）调整。
- 更新键（changeKey/decreaseKey/increaseKey）：直接修改keys[i]，然后根据变化上浮或下沉。
- 删除任意（delete）：交换到末尾，移除，然后上浮和下沉调整。
- 优势：所有操作均为O(log n)，索引映射提供O(1)访问，避免线性扫描。
这种结构优化了标准堆的局限性，后者更新任意元素需O(n)时间查找。
优化
- 时间复杂度优化：通过索引避免O(n)查找，更新操作从O(n + log n)降至O(log n)。在Dijkstra算法中，这可将总复杂度从O(V^2)优化到O((V+E) log V)。
- 空间优化：使用数组而非链表，紧凑存储；qp[]确保快速定位。
- 变体：可基于斐波那契堆（Fibonacci Heap）实现，摊销decreaseKey为O(1)，但实现复杂，常用于理论优化。
- 实际优化提示：在Java中，使用泛型确保类型安全；对于自定义键，重写
compareTo或提供Comparator。避免频繁更新以防堆退化。
图示
以下是索引堆的典型图示，展示数组表示和树结构，以及操作过程。
Java实现
以下是基于Princeton Algorithms的完整Java实现（IndexMinPQ），这是一个最小索引堆。代码包括详细注释，支持泛型键。
import java.util.Iterator;
import java.util.NoSuchElementException;
public class IndexMinPQ<Key extends Comparable<Key>> implements Iterable<Integer> {
private int maxN; // maximum number of elements on PQ
private int n; // number of elements on PQ
private int[] pq; // binary heap using 1-based indexing
private int[] qp; // inverse of pq - qp[pq[i]] = pq[qp[i]] = i
private Key[] keys; // keys[i] = priority of i
public IndexMinPQ(int maxN) {
if (maxN < 0) throw new IllegalArgumentException();
this.maxN = maxN;
n = 0;
keys = (Key[]) new Comparable[maxN + 1];
pq = new int[maxN + 1];
qp = new int[maxN + 1];
for (int i = 0; i <= maxN; i++)
qp[i] = -1;
}
public boolean isEmpty() {
return n == 0;
}
public boolean contains(int i) {
validateIndex(i);
return qp[i] != -1;
}
public int size() {
return n;
}
public void insert(int i, Key key) {
validateIndex(i);
if (contains(i)) throw new IllegalArgumentException("index is already in the priority queue");
n++;
qp[i] = n;
pq[n] = i;
keys[i] = key;
swim(n);
}
public int minIndex() {
if (n == 0) throw new NoSuchElementException("Priority queue underflow");
return pq[1];
}
public Key minKey() {
if (n == 0) throw new NoSuchElementException("Priority queue underflow");
return keys[pq[1]];
}
public int delMin() {
if (n == 0) throw new NoSuchElementException("Priority queue underflow");
int min = pq[1];
exch(1, n--);
sink(1);
qp[min] = -1;
keys[min] = null;
pq[n+1] = -1;
return min;
}
public Key keyOf(int i) {
validateIndex(i);
if (!contains(i)) throw new NoSuchElementException("index is not in the priority queue");
else return keys[i];
}
public void changeKey(int i, Key key) {
validateIndex(i);
if (!contains(i)) throw new NoSuchElementException("index is not in the priority queue");
keys[i] = key;
swim(qp[i]);
sink(qp[i]);
}
public void decreaseKey(int i, Key key) {
validateIndex(i);
if (!contains(i)) throw new NoSuchElementException("index is not in the priority queue");
if (keys[i].compareTo(key) == 0)
throw new IllegalArgumentException("Calling decreaseKey() with a key equal to the key in the priority queue");
if (keys[i].compareTo(key) < 0)
throw new IllegalArgumentException("Calling decreaseKey() with a key strictly greater than the key in the priority queue");
keys[i] = key;
swim(qp[i]);
}
public void increaseKey(int i, Key key) {
validateIndex(i);
if (!contains(i)) throw new NoSuchElementException("index is not in the priority queue");
if (keys[i].compareTo(key) == 0)
throw new IllegalArgumentException("Calling increaseKey() with a key equal to the key in the priority queue");
if (keys[i].compareTo(key) > 0)
throw new IllegalArgumentException("Calling increaseKey() with a key strictly less than the key in the priority queue");
keys[i] = key;
sink(qp[i]);
}
public void delete(int i) {
validateIndex(i);
if (!contains(i)) throw new NoSuchElementException("index is not in the priority queue");
int index = qp[i];
exch(index, n--);
swim(index);
sink(index);
keys[i] = null;
qp[i] = -1;
}
private void validateIndex(int i) {
if (i < 0) throw new IllegalArgumentException("index is negative: " + i);
if (i >= maxN) throw new IllegalArgumentException("index >= capacity: " + i);
}
private boolean greater(int i, int j) {
return keys[pq[i]].compareTo(keys[pq[j]]) > 0;
}
private void exch(int i, int j) {
int swap = pq[i];
pq[i] = pq[j];
pq[j] = swap;
qp[pq[i]] = i;
qp[pq[j]] = j;
}
private void swim(int k) {
while (k > 1 && greater(k/2, k)) {
exch(k, k/2);
k = k/2;
}
}
private void sink(int k) {
while (2*k <= n) {
int j = 2*k;
if (j < n && greater(j, j+1)) j++;
if (!greater(k, j)) break;
exch(k, j);
k = j;
}
}
public Iterator<Integer> iterator() {
return new HeapIterator();
}
private class HeapIterator implements Iterator<Integer> {
// create a new pq
private IndexMinPQ<Key> copy;
// add all elements to copy of heap
// takes linear time since already in heap order so no keys move
public HeapIterator() {
copy = new IndexMinPQ<Key>(pq.length - 1);
for (int i = 1; i <= n; i++)
copy.insert(pq[i], keys[pq[i]]);
}
public boolean hasNext() { return !copy.isEmpty(); }
public void remove() { throw new UnsupportedOperationException(); }
public Integer next() {
if (!hasNext()) throw new NoSuchElementException();
return copy.delMin();
}
}
}使用示例
public static void main(String[] args) {
IndexMinPQ<String> pq = new IndexMinPQ<String>(10);
pq.insert(0, "P");
pq.insert(1, "Q");
pq.insert(2, "E");
pq.decreaseKey(2, "C"); // 更新键
while (!pq.isEmpty()) {
System.out.println(pq.minKey() + " " + pq.delMin());
}
}输出：C 2\nP 0\nQ 1
此实现可扩展为最大堆（IndexMaxPQ），只需调整比较逻辑。