每日算法 — 使用java实现D-ary Heap：d叉堆与优先队列优化

二叉堆的局限

二叉堆（Binary Heap）是实现优先队列的经典数据结构，其插入和删除操作均为 O(log n)。然而在某些场景下，二叉堆并非最优选择：

缓存性能差：二叉堆每个节点只有两个子节点，树高为 log₂n。频繁的父子节点访问可能导致较多的缓存未命中
比较次数多：下沉操作（sift down）需要比较两个子节点，当比较操作代价高时（如大对象比较），这成为瓶颈
分支预测：二叉堆的条件分支较多，影响 CPU 流水线效率

d 叉堆的优势

d 叉堆（d-ary Heap）是每个节点最多有 d 个子节点的堆结构：

树高降低：树高为 log_d(n)，比二叉堆更矮
插入更快：插入只需向上比较 log_d(n) 次，当 d 大于 2 时比较次数减少
删除稍慢：删除需要比较 d 个子节点找到最小值，但缓存局部性更好
缓存友好：节点访问更集中，减少缓存未命中

最优 d 值的选择

最优的 d 值取决于具体场景：

d = 2（二叉堆）：通用场景，实现最简单
d = 3 或 4：当插入远多于删除时（如 Dijkstra 在稀疏图上）
d = 8 或 16：当比较代价很高时，或需要极致的缓存性能
d = n（近似）：退化为无序数组，插入 O(1)，删除 O(n)

实验表明，在 Dijkstra 算法中，d = 4 通常是稀疏图上的最优选择。

Java 实现

通用 d 叉堆

import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;

public class DaryHeap<T> {
    private final List<T> heap;
    private final Comparator<? super T> comparator;
    private final int d; // 每个节点的子节点数

    public DaryHeap(int d, Comparator<? super T> comparator) {
        if (d < 2) throw new IllegalArgumentException("d must be >= 2");
        this.d = d;
        this.comparator = comparator;
        this.heap = new ArrayList<>();
    }

    public DaryHeap(int d) {
        this(d, null);
    }

    @SuppressWarnings("unchecked")
    private int compare(T a, T b) {
        if (comparator != null) return comparator.compare(a, b);
        return ((Comparable<? super T>) a).compareTo(b);
    }

    // 获取父节点索引
    private int parent(int i) {
        return (i - 1) / d;
    }

    // 获取第 k 个子节点索引 (k 从 0 开始)
    private int child(int i, int k) {
        return d * i + k + 1;
    }

    /**
     * 插入元素
     */
    public void insert(T value) {
        heap.add(value);
        siftUp(heap.size() - 1);
    }

    private void siftUp(int i) {
        while (i > 0) {
            int p = parent(i);
            if (compare(heap.get(i), heap.get(p)) >= 0) break;
            swap(i, p);
            i = p;
        }
    }

    /**
     * 提取最小元素
     */
    public T extractMin() {
        if (heap.isEmpty()) return null;
        T min = heap.get(0);
        T last = heap.remove(heap.size() - 1);
        if (!heap.isEmpty()) {
            heap.set(0, last);
            siftDown(0);
        }
        return min;
    }

    private void siftDown(int i) {
        int n = heap.size();
        while (true) {
            int minIndex = i;
            // 在 d 个子节点中找到最小值
            for (int k = 0; k < d; k++) {
                int c = child(i, k);
                if (c < n && compare(heap.get(c), heap.get(minIndex)) < 0) {
                    minIndex = c;
                }
            }
            if (minIndex == i) break;
            swap(i, minIndex);
            i = minIndex;
        }
    }

    private void swap(int i, int j) {
        T temp = heap.get(i);
        heap.set(i, heap.get(j));
        heap.set(j, temp);
    }

    public T peek() {
        return heap.isEmpty() ? null : heap.get(0);
    }

    public int size() {
        return heap.size();
    }

    public boolean isEmpty() {
        return heap.isEmpty();
    }
}

基于 d 叉堆的 Dijkstra 算法

import java.util.*;

public class DijkstraWithDaryHeap {

    static class Edge {
        int to, weight;
        Edge(int to, int weight) { this.to = to; this.weight = weight; }
    }

    static class Node {
        int vertex, dist;
        Node(int v, int d) { vertex = v; dist = d; }
    }

    /**
     * 使用 d 叉堆优化的 Dijkstra 算法
     */
    public static int[] dijkstra(int n, List<List<Edge>> graph, int src, int d) {
        int[] dist = new int[n];
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[src] = 0;

        DaryHeap<Node> heap = new DaryHeap<>(d, Comparator.comparingInt(a -> a.dist));
        heap.insert(new Node(src, 0));

        while (!heap.isEmpty()) {
            Node cur = heap.extractMin();
            if (cur.dist > dist[cur.vertex]) continue;

            for (Edge e : graph.get(cur.vertex)) {
                int newDist = cur.dist + e.weight;
                if (newDist < dist[e.to]) {
                    dist[e.to] = newDist;
                    heap.insert(new Node(e.to, newDist));
                }
            }
        }

        return dist;
    }

    public static void main(String[] args) {
        int n = 6;
        List<List<Edge>> graph = new ArrayList<>();
        for (int i = 0; i < n; i++) graph.add(new ArrayList<>());

        graph.get(0).add(new Edge(1, 4));
        graph.get(0).add(new Edge(2, 2));
        graph.get(1).add(new Edge(2, 1));
        graph.get(1).add(new Edge(3, 5));
        graph.get(2).add(new Edge(3, 8));
        graph.get(2).add(new Edge(4, 10));
        graph.get(3).add(new Edge(4, 2));
        graph.get(3).add(new Edge(5, 6));
        graph.get(4).add(new Edge(5, 3));

        System.out.println("d=2 (二叉堆): " + Arrays.toString(dijkstra(n, graph, 0, 2)));
        System.out.println("d=4 (四叉堆): " + Arrays.toString(dijkstra(n, graph, 0, 4)));
        System.out.println("d=8 (八叉堆): " + Arrays.toString(dijkstra(n, graph, 0, 8)));
    }
}

性能对比测试

public class DaryHeapBenchmark {

    static void benchmarkInsertion(int n, int d) {
        DaryHeap<Integer> heap = new DaryHeap<>(d);
        Random rand = new Random(42);
        long start = System.nanoTime();
        for (int i = 0; i < n; i++) {
            heap.insert(rand.nextInt(n));
        }
        long time = System.nanoTime() - start;
        System.out.printf("d=%d, 插入 %d 个元素: %.2f ms%n", d, n, time / 1e6);
    }

    static void benchmarkMixed(int n, int d, int insertRatio) {
        DaryHeap<Integer> heap = new DaryHeap<>(d);
        Random rand = new Random(42);

        // 先插入一半
        for (int i = 0; i < n / 2; i++) {
            heap.insert(rand.nextInt(n));
        }

        long start = System.nanoTime();
        for (int i = 0; i < n; i++) {
            if (i % insertRatio == 0) {
                heap.extractMin();
            } else {
                heap.insert(rand.nextInt(n));
            }
        }
        long time = System.nanoTime() - start;
        System.out.printf("d=%d, 混合操作(删除率=1/%d): %.2f ms%n", d, insertRatio, time / 1e6);
    }

    public static void main(String[] args) {
        int n = 100000;
        System.out.println("=== 纯插入测试 ===");
        for (int d : new int[]{2, 3, 4, 8, 16}) {
            benchmarkInsertion(n, d);
        }

        System.out.println("
=== 混合操作测试 (插入:删除 = 9:1) ===");
        for (int d : new int[]{2, 3, 4, 8, 16}) {
            benchmarkMixed(n, d, 10);
        }
    }
}

Top-K 问题应用

public class TopKWithDaryHeap {

    /**
     * 使用 d 叉堆找前 K 大元素
     * 维护一个大小为 K 的最小堆
     */
    public static List<Integer> topK(int[] nums, int k, int d) {
        if (k <= 0) return new ArrayList<>();

        DaryHeap<Integer> minHeap = new DaryHeap<>(d);

        for (int num : nums) {
            if (minHeap.size() < k) {
                minHeap.insert(num);
            } else if (num > minHeap.peek()) {
                minHeap.extractMin();
                minHeap.insert(num);
            }
        }

        List<Integer> result = new ArrayList<>();
        while (!minHeap.isEmpty()) {
            result.add(minHeap.extractMin());
        }
        return result;
    }

    public static void main(String[] args) {
        int[] nums = {3, 2, 1, 5, 6, 4, 8, 7, 9, 10};
        System.out.println("Top 3: " + topK(nums, 3, 4));
    }
}

复杂度分析

操作	二叉堆 (d=2)	d 叉堆	说明
插入	O(log₂ n)	O(log_d n)	d 越大，比较次数越少
删除最小值	O(log₂ n)	O(d · log_d n)	需在 d 个子节点中找最小值
堆化	O(n)	O(n)	线性建堆对所有 d 成立
空间	O(n)	O(n)	与 d 无关

最优 d 值的数学分析

设每次比较代价为 C_cmp，每次交换代价为 C_swap。

插入代价约等于 log_d(n) · C_cmp
删除代价约等于 d · log_d(n) · C_cmp + log_d(n) · C_swap

当比较代价远大于交换代价时（如大对象、字符串比较），较大的 d 值更有利。

当交换代价与比较代价相当时，d = 2 或 3 通常是最佳选择。

应用场景

Dijkstra 算法：稀疏图上 d = 4 通常比二叉堆快 10-20%
A* 搜索：启发式评估代价高时，d 叉堆减少比较次数
Top-K 实时流：大数据流中维护 K 个最值元素
事件驱动模拟：如电路仿真、网络仿真中的事件队列
外部排序：k 路归并中 d = k 可减少比较开销
哈夫曼编码：优先队列构建频率树

总结

d 叉堆是对二叉堆的简单但有效的推广。通过调整分支因子 d，我们可以在插入效率和删除效率之间取得平衡，以适应不同的应用场景。在缓存敏感的环境中，d = 4 或 d = 8 的堆往往能提供超越二叉堆的实际性能。理解 d 叉堆有助于在算法实现中做出更精细的数据结构选择，特别是在图论算法和流式数据处理中。