每日算法 — 使用java实现二叉堆：完全二叉树实现优先队列与堆化操作

引言

优先队列（Priority Queue）是计算机科学中最常用的数据结构之一，广泛应用于任务调度、图算法（如 Dijkstra）、Top-K 问题等场景。而二叉堆（Binary Heap）是实现优先队列最经典、最高效的方式之一。本文将用 Java 从零实现一个完整的二叉堆，深入讲解上浮（sift-up）、下沉（sift-down）与堆化（heapify）的核心机制。

核心原理

二叉堆是一棵完全二叉树，分为大根堆（父节点 ≥ 子节点）与小根堆（父节点 ≤ 子节点）。利用完全二叉树的性质，可以用数组紧凑存储：

• 父节点索引：parent = (i - 1) / 2
• 左子节点索引：left = 2 * i + 1
• 右子节点索引：right = 2 * i + 2

核心操作：
– 插入：在末尾添加元素，然后上浮调整，时间复杂度 O(log n)
– 弹出堆顶：将堆顶与末尾交换，删除末尾，然后下沉调整，时间复杂度 O(log n)
– 堆化：从最后一个非叶子节点开始，逐个下沉，时间复杂度 O(n)

完整 Java 实现

import java.util.Arrays;

/**
 * 泛型二叉堆实现（小根堆）
 * @param <T> 元素类型，需实现 Comparable 接口
 */
public class BinaryHeap<T extends Comparable<T>> {

    private Object[] data; // 堆数组
    private int size;      // 当前元素个数
    private int capacity;  // 容量

    public BinaryHeap() {
        this.capacity = 16;
        this.data = new Object[capacity];
        this.size = 0;
    }

    public BinaryHeap(T[] arr) {
        this.capacity = Math.max(arr.length * 2, 16);
        this.data = Arrays.copyOf(arr, capacity);
        this.size = arr.length;
        heapify(); // 堆化
    }

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

    /**
     * 获取左子节点索引
     */
    private int leftChild(int i) {
        return 2 * i + 1;
    }

    /**
     * 获取右子节点索引
     */
    private int rightChild(int i) {
        return 2 * i + 2;
    }

    /**
     * 比较两个元素（小根堆：返回负数表示 a < b）
     */
    @SuppressWarnings("unchecked")
    private int compare(int i, int j) {
        T a = (T) data[i];
        T b = (T) data[j];
        return a.compareTo(b);
    }

    /**
     * 交换两个位置的元素
     */
    private void swap(int i, int j) {
        Object temp = data[i];
        data[i] = data[j];
        data[j] = temp;
    }

    /**
     * 上浮操作：将索引 i 处的元素向上调整
     */
    private void siftUp(int i) {
        while (i > 0) {
            int p = parent(i);
            if (compare(i, p) >= 0) break; // 已满足堆性质
            swap(i, p);
            i = p;
        }
    }

    /**
     * 下沉操作：将索引 i 处的元素向下调整
     */
    private void siftDown(int i) {
        while (true) {
            int minIdx = i;
            int left = leftChild(i);
            int right = rightChild(i);

            if (left < size && compare(left, minIdx) < 0) {
                minIdx = left;
            }
            if (right < size && compare(right, minIdx) < 0) {
                minIdx = right;
            }

            if (minIdx == i) break; // 已满足堆性质
            swap(i, minIdx);
            i = minIdx;
        }
    }

    /**
     * 堆化：将无序数组调整为堆结构
     * 时间复杂度 O(n)
     */
    private void heapify() {
        // 从最后一个非叶子节点开始下沉
        for (int i = parent(size - 1); i >= 0; i--) {
            siftDown(i);
        }
    }

    /**
     * 动态扩容
     */
    private void ensureCapacity() {
        if (size >= capacity) {
            capacity *= 2;
            data = Arrays.copyOf(data, capacity);
        }
    }

    /**
     * 插入元素
     */
    public void push(T val) {
        ensureCapacity();
        data[size] = val;
        siftUp(size);
        size++;
    }

    /**
     * 弹出堆顶元素
     */
    @SuppressWarnings("unchecked")
    public T pop() {
        if (size == 0) return null;
        T top = (T) data[0];
        data[0] = data[size - 1];
        size--;
        if (size > 0) siftDown(0);
        return top;
    }

    /**
     * 查看堆顶元素
     */
    @SuppressWarnings("unchecked")
    public T peek() {
        return size == 0 ? null : (T) data[0];
    }

    public int size() {
        return size;
    }

    public boolean isEmpty() {
        return size == 0;
    }

    /**
     * 原地堆排序：利用大根堆进行升序排序
     */
    public static <T extends Comparable<T>> void heapSort(T[] arr) {
        int n = arr.length;
        // 构建大根堆
        for (int i = (n - 2) / 2; i >= 0; i--) {
            siftDown(arr, i, n);
        }
        // 逐个将堆顶放到末尾
        for (int i = n - 1; i > 0; i--) {
            T temp = arr[0];
            arr[0] = arr[i];
            arr[i] = temp;
            siftDown(arr, 0, i);
        }
    }

    private static <T extends Comparable<T>> void siftDown(T[] arr, int i, int n) {
        while (true) {
            int maxIdx = i;
            int left = 2 * i + 1;
            int right = 2 * i + 2;
            if (left < n && arr[left].compareTo(arr[maxIdx]) > 0) maxIdx = left;
            if (right < n && arr[right].compareTo(arr[maxIdx]) > 0) maxIdx = right;
            if (maxIdx == i) break;
            T temp = arr[i];
            arr[i] = arr[maxIdx];
            arr[maxIdx] = temp;
            i = maxIdx;
        }
    }

    public static void main(String[] args) {
        // 测试优先队列
        BinaryHeap<Integer> heap = new BinaryHeap<>();
        int[] nums = {5, 3, 8, 1, 9, 2, 7};
        for (int x : nums) heap.push(x);

        System.out.print("小根堆弹出顺序: ");
        while (!heap.isEmpty()) {
            System.out.print(heap.pop() + " ");
        }
        System.out.println(); // 1 2 3 5 7 8 9

        // 测试堆化构造
        Integer[] arr = {5, 3, 8, 1, 9, 2, 7};
        BinaryHeap<Integer> heap2 = new BinaryHeap<>(arr);
        System.out.println("堆顶元素: " + heap2.peek()); // 1

        // 测试堆排序
        Integer[] sortArr = {5, 3, 8, 1, 9, 2, 7};
        heapSort(sortArr);
        System.out.println("堆排序结果: " + Arrays.toString(sortArr)); // [1, 2, 3, 5, 7, 8, 9]
    }
}

复杂度分析

关键洞察：堆化为何是 O(n)

堆化从最后一个非叶子节点开始逐个下沉。高度为 h 的节点最多有 ⌈n / 2^(h+1)⌉ 个，每个下沉耗时 O(h)。总时间为：

T(n) = Σ(h=0 to log n) ⌈n / 2^(h+1)⌉ * O(h) = O(n)

因为 Σ h / 2^h 收敛于常数 2。

应用场景

• Dijkstra 算法：用堆维护最短距离节点
• Top-K 问题：维护大小为 K 的堆
• 任务调度：按优先级取出任务
• 合并 K 个有序数组：K 路归并
• 堆排序：原地、不稳定排序

总结

二叉堆以其 O(log n) 的插入删除和 O(1) 的堆顶访问，成为优先队列的最佳实现之一。理解上浮与下沉的本质——即在父子之间维护堆序性质——是掌握所有堆变体（二项堆、斐波那契堆、配对堆）的基础。