堆
基本结构
堆是完全二叉树
-
除最后一层上面都是满的
-
最后一层的节点是从左到右按顺序的
例:
小顶堆:每个节点的值都小于(等于)左右子节点的值
如下就是一个小顶堆
存储
用数组来存。下标从1开始,根节点为1。若一个节点为x,则左儿子为2x,右儿子为2x+1(下标从0开始则为2x+1,2x+2)
操作
(以小根堆为例)
两个基本操作
down下沉:
比如修改了根节点的值后,需要重新调整,那么需要比这个点与两个子节点的值的大小,选择较小的与之交换,再拿这个点向下继续比较,以此类推
up上升:
同样的道理:比如修改最后一个节点的值,我需要跟它的父节点比较,如果小于父节点的值,交换。以此类推
两个基本操作的时间复杂度分析: 两个操作都与树的高度成正比,所以都为logn
五个操作: 用down,up操作来实现
- 插入一个数。在最后插入,进行up操作
- 求最小值。直接是根节点
- 删除最小值。删除根节点,把最后一个节点放到根节点的位置,down操作
- 删除任意一个元素。把最后一个节点放到这个位置,down,up(这里有三种情况,不动、上浮或下沉,虽然down,up都用了,但只会有一种情况,只会执行一个)
- 修改任意一个元素,同样道理,down,up
一个heap数组,size表示当前堆的大小。
堆排序
输入一个长度为 n 的整数数列,从小到大输出前 m 小的数。
输入格式
第一行包含整数 n 和 m。
第二行包含 n 个整数,表示整数数列。
输出格式
共一行,包含 m 个整数,表示整数数列中前 m 小的数。
数据范围
1≤m≤n≤1e5,
1≤数列中元素≤1e9
输入样例:
5 3
4 5 1 3 2
输出样例:
1 2 3
思路:
用到了完全二叉树的一个性质,下标从1开始,下标 <= n / 2的节点都是非叶子节点,大于 n / 2 的都是叶子节点,我们从非叶子节点开始往前逐一进行down操作。堆顶就是目前最小的值,每次取出堆顶的值也就是最小值,并进行上面5个操作当中的第3个操作,即删除最小值,重构堆。C++ 代码实现如下
代码:
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1e5 + 10;
int n, m, s;
int h[N];
void down(int u) {
int t = u;
if (2 * u <= s && h[2 * u] < h[t]) t = 2 * u;
if (2 * u + 1 <= s && h[2 * u + 1] < h[t]) t = 2 * u + 1;
if (u != t) swap(h[u], h[t]), down(t);
}
int main()
{
cin >> n >> m;
s = n;
for (int i = 1; i <= n; i ++ ) scanf("%d", &h[i]);
for (int i = n / 2; i >= 1; i -- ) {
down(i);
}
while (m -- ) {
printf("%d ", h[1]);
h[1] = h[s -- ];
down(1);
}
return 0;
}
文章评论