202607011314堆（heap）

堆是什么？

堆是一种二叉树，大顶堆是指父亲大于等于孩子的堆，堆顶为最大值。小顶堆是指父亲小于等于孩子的堆，堆顶为最小值。为节省内存，一般用数组模拟二叉树。对于 0-indexed 数组（第一个下标是 0），父子坐标关系如下，

parent = (child - 1) / 2
child_1 = 2 * parent + 1
child_2 = child_1 + 1 = 2 * parent + 2

堆是一个弱序，并没有像二叉搜索树（BST）那么严格的有序，

二叉搜索树：左子树 < 父节点 < 右子树
二叉堆：左右孩子 < 父节点。但左右孩子之间的关系不保证有序，可以混杂。由此可得，父节点 > 左右子树。

flowchart TB

subgraph 二叉搜索树
	direction TB
    a[50]
    b[30]
    c[70]
    d[20]
    e[40]
    f[60]
    g[80]

    a --> b
    a --> c
    b --> d
    b --> e
    c --> f
    c --> g
end
subgraph 二叉堆
	direction TB
    A[80]
    B[40]
    C[70]
    D[20]
    E[30]
    F[60]
    G[50]

    A --> B
    A --> C
    B --> D
    B --> E
    C --> F
    C --> G
    
	style A fill:#f9f,stroke:#333,stroke-width:2px
	style B fill:#f9f,stroke:#333,stroke-width:2px
	style C fill:#f9f,stroke:#333,stroke-width:2px
	style D fill:#f9f,stroke:#333,stroke-width:2px
	style E fill:#f9f,stroke:#333,stroke-width:2px
	style F fill:#f9f,stroke:#333,stroke-width:2px
	style G fill:#f9f,stroke:#333,stroke-width:2px
end

因此，维护堆的性质相对比较轻量。要维护堆，一般涉及以下几种操作，

- bubble_up(array, i); // 在堆尾插入元素，上浮到合适位置，使得堆的性质得以保持
- bubble_down(array, i); // 弹出堆顶，将堆尾元素换上来，进行下沉（堆化），过程中维持堆的性质
- get_top(); // 返回堆顶，一般就是array[0]
- pop(); // 弹出堆顶，此时要将堆尾换上来，进行下沉以维护堆的性质

C++的标准库除了priority_queue这种封装好的优先队列外，还提供了下面几个单独的接口操作堆：

push_heap：将范围内最后一个元素入堆
pop_heap：将堆顶换到堆尾，然后堆的容量减 1，维护堆的性质。等效于将堆顶弹出，放在了原来的堆尾（现在不是了，因为堆容量减 1 了）
is_heap：判断范围内元素是否满足堆的性质
sort_heap：把一个堆转换成有序数组，堆的性质不在维持
make_heap：把范围内元素转换为堆

而 priority_queue 也仅提供如下接口：

push：元素入堆
pop：弹出堆顶
top：返回堆顶

注意

std::priority_queue 默认是大顶堆，即堆顶元素是最大值。小顶堆可通过 std::priority_queue<int, vector<int>, greater<int>> 来获得。同样的，std::push_heap 之类的接口默认也都是按大顶堆维护。

为什么用堆尾元素填补？

不破坏结构：堆必须保持完全二叉树，直接拿末尾元素补到根节点，不会留下中间空洞。
代价最低：数组里删末尾元素是 $O (1)$ ，如果拿中间元素来补位，还要额外移动很多元素。
后续好调整：补到堆顶后，只需要从上往下做一次下沉，就能恢复堆性质，时间复杂度是 $O (lo g n)$ 。

为什么用数组模拟？

如果像BST一样，那么指针占用的空间，甚至比我们感兴趣的数据要多，这是一种内存的浪费。
二叉堆是一棵完全二叉树，中间没有空洞，只有最后一层可以不满。这样的结构也有利于用数组去模拟，通过下标来隐性表示父子关系。

用数组模拟的代价

无法在不浪费空间的情况下，有效存储任意拓扑结构的二叉树。因为节点间靠下标确定父子关系，如果多个内部节点只有左孩子或右孩子，数组中间会有很多空洞（hole）。
无法像二叉树那样通过指针挪动一整个子树。

因此，不是所有的二叉树都适合用数组模拟。但在这里，堆很适合！

设高度为 $h$ 的二叉堆有 $n$ 个节点，则

#nodes of full binary tree with height (h - 1) = i = 0 \sum h - 1 2^{i} = 2^{h} - 1 #nodes of full binary tree with height h = i = 0 \sum h 2^{i} = 2^{h + 1} - 1 ⟹ 2^{h} - 1 < n \leq 2^{h + 1} - 1 ⟹ 2^{h} \leq n < 2^{h + 1} (since n \in N) ⟹ h \leq l g n < h + 1 ⟹ h = ⌊ l g n ⌋

实现示例

要维护堆的性质，最重要的就是下沉和上浮两个操作。同时再复习一遍堆的性质（不失一般性，假设是大顶堆）：父亲支配孩子。即父节点不能比孩子节点还小，父节点大于等于子节点。

下沉：父亲如果比孩子小，找到父子三者（或者二者）之间的最大值，把大的换上去，小的换下来。继续比较换下来之后的元素和其儿子的大小。
上浮：叶子节点变更时，孩子如果比父亲大，就把大的换上去，小的换下来。继续比较换上去的元素和其父亲的大小。

inline size_t parent(size_t i) {
    if (i > 0) {
        return (i - 1) / 2;
    }
    return 0;
}
 
// left child of i
inline size_t lchild(size_t i) {
    return 2 * i + 1;
}
 
void bubble_down(std::vector<int>& v, size_t i, size_t heap_size) {
    while (i < heap_size) {
        size_t c = lchild(i);
        if (c >= heap_size) {
            return;
        }
 
        // get top element between parent and two children
        size_t top_idx = i;
        for (size_t j = c; j <= c + 1; ++j) {
            if (j < heap_size && v[top_idx] < v[j]) {
                top_idx = j;
            }
        }
        if (top_idx != i) { // got a top elem
            std::swap(v[top_idx], v[i]);
            i = top_idx;
        } else { // parent already dominates children, which satisfies heap property
            break;
        }
    }
}
 
void bubble_up(std::vector<int>& v, size_t i) {
    while (i > 0) {
        size_t p = parent(i);
        if (v[p] < v[i]) {
            std::swap(v[p], v[i]);
            i = p;
        } else { // parent already dominates children, which satisfies heap property
            break;
        }
    }
}

有了这两个操作，我们就可以继续其他的操作了。

// 堆尾加入新元素，进行上浮
void push_heap(std::vector<int>& v, size_t heap_size, int e) {
    v.resize(heap_size + 1);
    v[heap_size] = e;
    bubble_up(v, heap_size);
}
 
// 交换堆顶和堆尾，堆容量减1，从堆顶下沉。等价于弹出堆顶。
void pop_heap(std::vector<int>& v, size_t heap_size) {
    if (v.empty()) {
        throw std::runtime_error("pop on empty heap!");
    }
    std::swap(v[0], v[heap_size-1]);
    bubble_down(v, 0, heap_size - 1);
}
 
// 将数组堆化，heapify.
void make_heap(std::vector<int>& v) {
    const size_t heap_size = v.size();
    if (heap_size < 2) {
        return;
    }
    size_t last_parent = parent(heap_size - 1); // 大于last_parent的均为叶子，不用下沉了
    for (size_t i = last_parent + 1; i > 0; --i) {
        bubble_down(v, i - 1, heap_size);
    }
}

以及利用堆进行排序，著名的 heap sort 算法。

参考示例：https://leetcode.cn/problems/take-gifts-from-the-richest-pile/solutions/2501655/yuan-di-dui-hua-o1-kong-jian-fu-ti-dan-p-fzdh/comments/3184803/

复杂度

bubble_down/bubble_up 的复杂度和堆高成正比，所以是 $O (h) = O (l g n)$
建堆调用了 n/2 次 bubble_down，看起来复杂度是 $O (n l g n)$ ，其实复杂度是 $O (n)$ ，想一想为啥？
获得最值显然是 $O (1)$ ，因为堆顶就是最值，返回堆顶就可以了
push/pop 均调用一次 bubble_up/bubble_down，所以复杂度是 $O (l g n)$
堆排序，执行 n 次 bubble_down，所以是 $O (n l g n)$

Learn2Live

随机笔记

202306062013SSL-vs-TLS

202503071009不要直接改系统的glibc版本

nice_phrase_in_paper

Linux的休眠

202509291120deploy-github-page

探索

202607011314堆（heap）

堆是什么？

实现示例

复杂度

关系图谱

目录

反向链接