Casey

堆

最近更新：2025-04-03 | 字数总计：902 | 阅读估时：3分钟 | 阅读量：次

堆是一棵完全二叉树，且其中所有节点的值都大于（或是小于）其子节点。

自建堆

这里以大根堆为例，演示如何自建堆并实现堆中的操作。

存储

由于堆是棵完全二叉树，因此可以使用顺序结构存储，如下。

1	int heap[N], size;

其中的 size 为容量。堆顶元素的序号为 1，堆中的第 i 个元素子节点的序号为 2 * i 和 2 * i + 1。

基本操作

堆中最基本的操作为将序号为 i 的元素根据堆的定义进行向上及向下调整。

向上调整时，节点只需要和其父节点的值进行比较，若比父节点大，则交换，并递推向上调整。向上调整的前提是只有当前节点的值是可能不满足定义的，而其他节点都满足。因此向上调整多用于堆中元素的插入、修改操作。

void up(int i) {
    if (i == 1 || heap[i] <= heap[i / 2]) {
        return; // 没有父节点或是满足定义时返回
    }
    swap(heap[i], heap[i / 2]); // 交换
    up(i / 2); // 递推向上调整
}

向下调整时需要同其两个子节点的值进行比较，并递推向下调整。注意，这里向下调整需要注意判断子节点是否存在。

void down(int i) {
    if (i * 2 > size || (heap[i] >= heap[i * 2] && (i * 2 + 1 > size || heap[i] >= heap[i * 2 + 1]))) {
        return; // 没有子节点或是满足定义时返回
    }
    if (i * 2 + 1 > size || heap[i * 2] >= heap[i * 2 + 1]) {
        swap(heap[i], heap[i * 2]);
        down(i * 2);
    }
    else {
        swap(heap[i], heap[i * 2 + 1]);
        down(i * 2 + 1);
    }
}

以上的代码在实际中可以进行优化，使用循环及更易读的方式来写，这里不作拓展。

构造操作

建堆时对序列自底向上进行向下调整，使其满足堆的定义，如下。

为什么不是自顶向下调整？自顶向下调整相当于逐个向堆中插入元素，效率相比于自底向上调整效率更低。

void build() {
    for (int i = size / 2; i >= 1; i--) {
        down(i);
    }
}

自建堆的插入是将新加入的元素放到堆尾，并对新加入的元素作向上调整，以满足堆的定义，如下。

void insert(int x) {
    size++;
    heap[size] = x;
    up(size);
}

自建堆删除堆顶是将堆顶元素同堆尾元素互换，将堆的容量减一，并对堆顶作向下调整，如下。

void delete_max() {
    heap[1] = heap[size];
    size--;
    down(1);
}

自建堆删除序号为 i 元素的操作类似于删除堆顶，但此时需要执行向上和向下调整，如下。

void delete_i(int i) {
    heap[i] = heap[size];
    size--;
    up(i);
    down(i);
}

修改堆中序号为 i 的元素时，同样需要执行向上和向下调整，如下。

void modify(int i, int x) {
    heap[i] = x;
    up(i);
    down(i);
}

大根堆堆顶元素为序列中的最大值，取最大时直接返回，如下。

1
2
3

int get_max() {
    return heap[1];
}

STL 中的堆

priority_queue 容器

C++ 可以使用 STL 中的 priority_queue 实现堆，如下。

1 2	priority_queue<int> max_heap; // 大根堆 priority_queue<int, vector<int>, greater<int>> min_heap; // 小根堆

priority_queue 默认为大根堆。因为默认的 less 会使数值更小的优先级更小，而 priority_queue 是使优先级更高的先输出（在堆顶），因此其默认为大根堆。

priority_queue 的基本操作如下。

1
2
3

max_heap.push();
max_heap.pop();
max_heap.top();

heap 函数

STL 中还提供相关函数，对可迭代容器实现堆相关操作。

make_heap()
heap_push()
heap_pop()
sort_heap()
is_heap()
is_heap_until()

（后续完善…）

2025-04-03 该篇文章被 Casey 打上标签: 算法 C++ 归为分类: 学习