算法笔记-堆

__er · 2023-01-28 20:10:04 · 题解

堆（ \rm Heap）是计算机科学中一类特殊的数据结构的统称。堆通常是一个可以被看做一棵树的数组对象。堆总是满足下列性质：

• 堆中某个结点的值总是不大于或不小于其父结点的值；
• 堆总是一棵完全二叉树。

上面提到的性质 1 中，如果不大于即为大根堆，如果不小于即为小根堆，看图：

如上是大根堆。

如上是小根堆。

堆实质上是一颗二叉树，二叉树的存储使用一维数组，编号为 i 的结点的父结点编号为 \left\lfloor\dfrac{i}{2}\right\rfloor，左儿子编号为 2 \times i，右儿子编号为 2 \times i +1。

因为性质 1，堆还能用于排序。

手写堆：

手写堆虽然麻烦，但是效率比较高，尽管有替代品但是这是理解堆及二叉树思想的最好方法，以下讲解为小根堆。

首先三个 #define

#define f(x) (((x)-1)/2)
#define l(x) ((x)*2+1)
#define r(x) ((x)*2+2)

三个宏定义分别表示 x 结点的父亲，左儿子，右儿子（+1+2 为个人喜好）。

操作如下：

1. push 向堆中压入一个元素
2. pop （也有写法写作 del(\tt delete)）从堆中弹出（删除）堆顶元素
3. top 查询堆顶元素

• push：

压入一个元素，首先堆元素数量（大小）siz 需要 +1，从堆底加入，如果不满足小根堆的性质（见堆的性质 1），则不断上调直至满足性质（即父结点小于当前结点）。

例如对此堆执行 push(0)

首先在堆底插入：

因为 3>0 所以上调：

因为 1>0 所以继续上调：

因为 0<1 所以操作结束。

push 函数为：

void push(int x) {
    int pos = siz++;//在堆底插入
    /*上调操作*/while (pos > 0) {
        if (heap[f(pos)] <= x) {//如果父结点小于当前结点，满足性质
            break;//停止
        }
        heap[pos] = heap[f(pos)], pos = f(pos);//互换位置
    }
    heap[pos] = x;//确定位置后赋值
    return;
}

• pop：

首先使用堆底结点替换掉堆顶元素（先删掉堆顶元素），然后对替换上来的结点不断下调直至满足性质。

我们对刚刚进行过 push 操作的堆进行 pop 操作：

执行 pop 使用 3 代替 0 变为：

因为 3>1 所以下调：

因为 1 已经是根结点（整个堆/整棵树中最小的），所以操作结束。

pop 函数为：

void pop() {
    int pos = 0, x = heap[--siz];
    while (l(pos) < siz) {
        int t = (heap[l(pos)] < heap[r(pos)]) ? l(pos) : r(pos);//找较小儿子
        /*下调操作*/if (heap[t] >= x) {
            break;
        }
        heap[pos] = heap[t], pos = t;
    }

    heap[pos] = x;//同上
    return;
}

• top：

返回堆顶元素，也就是最小的元素。

执行 top ，返回顶端的 1 且 1 为堆中的最小元素。

top 函数为：

int top() {
    return heap[0];
}

代码：

此代码可过模板题

#include <bits/stdc++.h>
#define f(x) (((x)-1)/2)
#define l(x) ((x)*2+1)
#define r(x) ((x)*2+2)
#define JS ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr)
using namespace std;
int heap[1000001], siz;

void push(int x) {
    int pos = siz++;
    while (pos > 0) {
        if (heap[f(pos)] <= x) {
            break;
        }
        heap[pos] = heap[f(pos)], pos = f(pos);
    }
    heap[pos] = x;
    return;
}

void pop() {
    int pos = 0, x = heap[--siz];
    while (l(pos) < siz) {
        int t = (heap[l(pos)] < heap[r(pos)]) ? l(pos) : r(pos);
        if (heap[t] >= x) {
            break;
        }
        heap[pos] = heap[t], pos = t;
    }
    heap[pos] = x;
    return;
}

int top() {
    return heap[0];
}
int T, num, op;

int main() {
    JS;
    cin >> T;
    while (T--) {
        cin >> op;
        if (op == 1) {
            cin >> num;
            push(num);
        }
        if (op == 2) {
            cout << top() << '\n';
        }
        if (op == 3) {
            pop();
        }
    }
    return 0;
}

STL

STL 实现的堆有两种：

1. std::heap（堆）

2. std::priority_queue（优先队列）

• std::heap

在头文件 <algotithm> 中，使用 heap 需 include 或使用万能头。

make_heap()：

先指定一个容器的范围建堆，常用 vector，建堆执行后最大值在所给范围的最左端，其他值并未排序。

使用方法：make_heap(v.begin(),v.end,_Comp/*自定义比较函数，非必要*/);v 代表 vector 的名称

v.push_back() 压入一个元素，但元素并未排序（没有进行上调操作）。

push_heap() 对刚刚压入元素的堆执行上调，用法：push_heap(v.begin(),v.end(),cmp/*自定义比较函数，非必要*/);

pop_heap() 等价于手写堆的 pop 弹出（删除）堆顶（最大值），用法：pop_heap(v.begin(),v.end(),cmp/*自定义比较函数，非必要*/);

sort_heap() 执行堆排序，可得到一个有序序列，用法：sort_heap(v.begin(),v.end(),cmp/*自定义比较函数，非必要*/);

• std::priority_queue：

底层使用 std::heap 实现。

定义：priority_queue<T/*数据类型*/,Cotainer/*容器*/,Compare/*比较规则，可以使用自定义*/>

自带两种比较函数：

1. greater<T/*数据类型*/> 小根堆
2. less<T/*数据类型*/> 大根堆

操作：

push() 压入元素，构造完毕后压入（执行上调）。

emplace()同时执行构造和压入（执行上调）。

pop() 弹出堆顶。

top() 返回堆顶元素。

size() 返回堆大小（元素个数）。

empty() 查询堆是否为空，返回值为 bool 类型，堆为空时返回 true，否则返回 false。

使用方法都为：q.成员函数() _q 代表 priority_queue 的名称_。

pb__ds

pb__ds （\tt Policy-Based\ Data\ Structures）库包含于 __gnu_pbds 命名空间里，使用其中的堆需要两个头文件：

#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/priority_queue.hpp> 

万能头不能解决问题，<bits/stdc++.h> 只包含标准库的所有头文件，而pb__ds库是扩展库！

定义方法：

__gnu_pbds::priority_queue<T, Compare = std::less<T>, Tag = __gnu_pbds::pairing_heap_tag, Allocator = std::allocator<char>>

Tag 决定了堆的类型，共有五种堆：

1. __gnu_pbds::pairing_heap_tag 配对堆 push,pop 效率较好，push,join 复杂度为 \mathcal{O}(1)，但 pop 的最差复杂度很高。
2. __gnu_pbds::binary_heap_tag 二叉堆 push,pop 效率高。
3. __gnu_pbds::binomial_heap_tag 二项堆 push,pop 效率较差，但 pop 函数的时间复杂度最慢只有亚线性。
4. __gnu_pbds::rc_binomial_heap_tag 冗余计数二项堆 相比二项堆 push,pop 更差，但是 push \mathcal{O}(1)。
5. __gnu_pbds::thin_heap_tag 斐波那契堆（注：合并堆的复杂度与斐波那契堆不同）适合图论算法，在一些方面甚至优于斐波那契堆，不过由于封装过紧，常数大，反而在非图论算法上最劣。

操作：

1. push() 压入元素。
2. pop() 弹出堆顶元素。
3. top() 返回堆顶元素。
4. empty() 返回是否为空（返回值 bool 类型）。
5. size() 返回堆大小。
6. modify(iterator, key) 修改迭代器位置的值。
7. erase(iterator) 删除迭代器位置的值。
8. join() 把另一个堆和当前堆合并并清空被合并的堆。

时间复杂度：

斐波那契堆：

斐波那契堆是堆的集合，比二叉堆拥有更高的效率，但是由于常数比较大而且不好写所以不常用。

堆优化 dijkstra：

每次更新最短距离的时候把对应的元素上调，每次从小根堆中取堆顶做下一次要用的顶点，从复杂度 \mathcal{O}(V^2) 优化到 \mathcal{O}(E \log V)。

复杂度：

除建堆和 top() 操作是 \mathcal{O}(1) 外，其余操作全部为 \mathcal{O}(\log n)。

例题：

P3378 【模板】堆

P3377 【模板】左偏树（可并堆)

P1628 合并序列