模拟堆
一些概念:
- 堆是一棵完全二叉树
- 小根堆:任意一棵子树,根节点都小于等于左右子树的点
1. 如何手写一个堆?
- 插入一个数
- 求集合中的最小值
- 删除最小值
- 删除任意一个元素
- 修改任意一个元素
2. 堆的核心操作:up() 和 down()
堆的核心操作只有两个:
up()
:一个数变小了,在二叉树中需要往上浮
c++
void up(int u)
{
while(u / 2 > 0 && h[u / 2] > h[u]) {
u /= 2;
}
}
down()
:一个数变大了,在二叉树中需要往下沉
c++
void down(int u)
{
int t = u;
if (u * 2 <= sz && h[u * 2] < h[t]) t = u * 2;
if (u * 2 + 1 <=sz && h[u * 2 + 1] < h[t]) t = u * 2 + 1;
if (t != u) {
swap(h[t], h[u]);
down(t):
}
}
down
操作示意图:
- 首先我们有一个小根堆
text
1
/ \
3 4
/ \ / \
3 5 4 5
- 将根节点从
1
改为6
6
/ \
3 4
/ \ / \
3 5 4 5
此时小根堆的状态被破坏,需要通过down
操作重新建立新的小根堆
down
操作过程
text
6
/ \
3 4
/ \ / \
3 5 4 5
6和儿子(3 和 4)比较,跟较小(3)的交换位置
3
/ \
6 4
/ \ / \
3 5 4 5
6继续和它的儿子(3 和 5)比较,跟较小(3)的交换位置
3
/ \
3 4
/ \ / \
6 5 4 5
结束,重新建立起小根堆
up
操作类似down
操作。
3. 堆的实现
约定:这里介绍如何用数组模拟小根堆。
堆的底层是一棵完全二叉树,我们使用下标从1
开始一维数组模拟堆。下标为x
的元素,它的左儿子下标是2x
,右儿子下标是2x+1
,它的父节点下标是x/2
- 下标为什么从
1
开始?
习惯问题,下标也可以从
0
开始。
我们通过down()
和up()
这两个操作实现堆的功能:
- 插入一个数
c++
heap[++ size] = x;
up(x);
- 堆中最小值
c++
heap[1];
- 删除最小值
c++
heap[1] = heap[size];
size --;
down(1);
- 用最后一个数覆盖堆顶元素
size --
down(1)
为什么这样做?
我们用数组模拟堆,堆顶元素位于
heap[1]
,数组中删除第一个数比较麻烦但删除最后一个数非常方便,因此选择用最后一个数覆盖第一个数,然后执行down(1)
操作
- 删除任意(第
k
个)元素
c++
heap[k] = heap[size]; size --; down(k); up(k);
为什么要通知执行down(k)
和up(k)
?
用最后一个数覆盖第
k
个数,我们不知道此时是需要down还是需要up,因此,直接调用这两个函数,它们会判断是否需要执行down和up
- 修改任意(第
k
个数)元素
c++
heap[k]=x;
down(k);
up(k);
实现:
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int n, m;
int h[N], sz;
void down(int u)
{
int t = u;
if (u * 2 <= sz && h[u * 2] < h[t]) t = u * 2;
if (u * 2 + 1 <= sz && h[u * 2 + 1] < h[t]) t = u * 2 + 1;
if (t != u) {
swap(h[u], h[t]);
down(t);
}
}
int main()
{
cin >> n >> m;
for (int i = 1; i <= n; i ++) cin >> h[i];
sz = n;
// 建堆
for (int i = n / 2; i > 0; i --) {
down(i);
}
while(n --) {
cout << h[1] << ' ';
h[1] = h[sz];
sz --;
down(1);
}
return 0;
}
- 为什么第 16 行的建堆方式时间复杂度为
O(n)
?
。。。