二叉堆核心原理及可视化

raw/articles/2026/05/二叉堆基础

一句话总结

二叉堆是一种能够动态排序的数据结构，核心操作是 sink（下沉）和 swim（上浮），用于维护堆性质。主要应用有两个：优先级队列（Priority Queue）和堆排序（Heap Sort）。

核心内容

一、二叉堆概览

定义：二叉堆是一种特殊的完全二叉树，存储在数组中（而非链表）。

数组索引与树节点关系（索引 0 空着不用）：

int parent(int root) { return root / 2; }
int left(int root) { return root * 2; }
int right(int root) { return root * 2 + 1; }

![[images/二叉堆-1.png]]

两种类型：

• 最大堆：每个节点都 ≥ 其子节点，堆顶是最大元素
• 最小堆：每个节点都 ≤ 其子节点，堆顶是最小元素

二、优先级队列

基于二叉堆实现，主要 API：

• insert(Key e) - 插入元素
• delMax() - 删除并返回最大元素
• max() - 查看最大元素

三、核心操作：swim 和 sink

上浮（swim）：当节点比父节点大时，需要上浮

private void swim(int k) {
    while (k > 1 && less(parent(k), k)) {
        exch(parent(k), k);
        k = parent(k);
    }
}

![[images/二叉堆-swim.gif]]

下沉（sink）：当节点比子节点小时，需要下沉

private void sink(int k) {
    while (left(k) <= N) {
        int older = left(k);
        if (right(k) <= N && less(older, right(k)))
            older = right(k);
        if (less(older, k)) break;
        exch(k, older);
        k = older;
    }
}

![[images/二叉堆-sink.gif]]

四、优先级队列实现

插入操作：先加到堆底，再上浮到正确位置

public void insert(Key e) {
    N++;
    pq[N] = e;
    swim(N);
}

![[images/二叉堆-insert.gif]]

删除最大元素：堆顶与堆底交换，删除原堆顶，再下沉新堆顶

public Key delMax() {
    Key max = pq[1];
    exch(1, N);
    pq[N] = null;
    N--;
    sink(1);
    return max;
}

![[images/二叉堆-delete.gif]]

五、复杂度分析

操作	时间复杂度	说明
insert	O(log K)	K 为堆中元素总数，最多上浮树的高度
delMax	O(log K)	最多下沉树的高度
max	O(1)	直接返回堆顶

树的高度为 log K，因此核心操作都是对数时间。

相关概念

• 二叉树：二叉堆是完全二叉树的特殊形式
• 二叉搜索树：另一种常见二叉树，但性质不同（BST 左小右大）
• 优先级队列
• 堆排序

相关实体

• labuladong：算法学习平台作者