手写堆

CSP-J · 编程模板 · 片段 · cpp · 难度 4/5 · 共 686 字

数组实现的完全二叉树，上浮下沉维护堆

数据结构
手写堆

前置内容

二叉树遍历

正文

// 手写堆：用数组实现的完全二叉树
// 父 i 的子节点在 2i、2i+1
// 以小根堆为例：上浮 + 下沉
#include <cstdio>
int h[100005], sz = 0;
// 上浮：与父比较，小则交换
void up(int i) {
    while (i > 1 && h[i] < h[i / 2]) {
        int t = h[i];
        h[i] = h[i / 2];
        h[i / 2] = t;
        i /= 2;
    }
}
// 下沉：与较小子节点交换
void down(int i) {
    while (i * 2 <= sz) {
        int c = i * 2;
        // 选更小的右子节点
        if (c + 1 <= sz && h[c + 1] < h[c])
            c++;
        if (h[i] <= h[c]) break;
        int t = h[i];
        h[i] = h[c];
        h[c] = t;
        // 继续往下
        i = c;
    }
}
int main() {
    // 弹出堆顶：末尾补位再下沉
    int top = h[1];
    h[1] = h[sz--];
    down(1);
    printf("%d", top);
    return 0;
}

手写堆

前置内容

正文

CSP-J · 编程模板的其它内容