二叉堆 (Binary Heap)

基于完全二叉树的高效优先队列实现，支持 $O(\log N)$ 级的最值维护

什么是二叉堆？

二叉堆是一种特殊的完全二叉树，存储在一维数组中。它满足如下性质：

父子节点索引关系（0-Indexed）

设节点在一维数组中的索引为 $i$，则：

  • 其左孩子节点索引为：$2i + 1$
  • 其右孩子节点索引为：$2i + 2$
  • 其父节点索引为：$\lfloor (i - 1) / 2 \rfloor$
点击"插入元素"或"取出堆顶"按钮观察二叉堆的动态结构调整过程。

完全二叉树形态

一维数组物理存储形态

C++ 核心代码对照

二叉堆 (大根堆) C++ 实现
class MaxHeap {
private:
    vector<int> heap;

    // 向上调整：用于插入元素后维护堆
    void siftUp(int i) {
        while (i > 0) {
            int p = (i - 1) / 2;
            if (heap[i] <= heap[p]) break;
            swap(heap[i], heap[p]); // 与父节点交换
            i = p;
        }
    }

    // 向下调整：用于提取堆顶后维护堆
    void siftDown(int i) {
        int n = heap.size();
        while (2 * i + 1 < n) {
            int left = 2 * i + 1;
            int right = 2 * i + 2;
            int largest = left;
            
            // 找出左、右孩子中较大者
            if (right < n && heap[right] > heap[left]) {
                largest = right;
            }
            if (heap[i] >= heap[largest]) break;
            
            swap(heap[i], heap[largest]); // 与较大孩子交换
            i = largest;
        }
    }

public:
    void insert(int val) {
        heap.push_back(val); // 放到末尾
        siftUp(heap.size() - 1); // 向上调整
    }

    int extractMax() {
        if (heap.empty()) return -1;
        int maxVal = heap[0];
        heap[0] = heap.back(); // 尾部移到头部
        heap.pop_back();
        siftDown(0); // 向下调整
        return maxVal;
    }
};