堆(heap):笔记
什么是
是一个二叉树/完全二叉树;
根节点是最小值(小根堆)/最大值(大根堆)
每个节点的值小于其左右孩子;
功能
1.插入一个数
2.求集合中最大(小)值
3.删除最小(大)值
4.删除任意一个元素
5.修改任意一个元素
存储方式
一维数组存储;
下标从1开始;
下标为x的节点,左孩子为2x,右孩子为2x+1;
实现堆的两个基本操作
1.down(x):将一个大于孩子值的根节点向下移动,找到本该的位置
2.up(x);将一个小于根节点值的孩子节点向上移动,找到本来的位置
用两个基操实现功能
1.插入x
heap[++size] = x
up(size);
2.求最小值
heap[1]
3.删最小值
heap[1] = heap[size]
size--;
down(1);
4.删除第k个元素
heap[k] = heap[size]
size--
down(k),up(k);
代码实现
建立堆O(n):
for(int i=1;i<=n;i++) cin >> h[i];
for(int i=n/2;i;i--) down[i]; //n/2是倒数第二层,倒数第一层不需要down
down函数
void down(int u)
{
int t = u; //用t存储根左右三个节点中最小的;
if(2*u <= size && h[2*u] < h[t]) t = 2*u;
if(2*u + 1 <= size && h[2*u+1] < h[t]) t = 2*u+1;
if(u != t)
{
swap(h[u],h[t]);
down(t); // 继续往下down
}
}
up函数
void up(int u)
{
while(u/2 && h[u/2] > h[u])
{
swap(h[u/2],h[u]);
u /= 2;
}
}