堆的定义
n个元素的序列{k1,k2,···,kn}当且仅当满足以下关系时,称之为堆:
前者称为小根堆,后者称为大根堆。
接下来,我们以小根堆为例对堆进行总结。
根据堆的定义,我们可以将堆表示成完全二叉树,给出一个小根堆的例子如下:
父节点一定小于等于两个孩子节点。
堆的存储
虽然用完全二叉树表示堆非常直观,但实际编程时通常采用数组模拟堆,依据下标处理相关联的元素。
const int N = 1e5 + 10;
int h[N]; //堆
int mySize; //最末端的元素的下标
也经常使用C++的priority_queue来模拟堆。
堆的基础操作
实现一个堆的核心:
- down,节点的下沉操作
- up,节点上升操作
down
对一个节点,如果它大于某个孩子节点,就应该将该节点下沉,即与它最小的孩子节点交换位置,以满足堆的定义。
void down(int u) //u为节点的下标
{ //递归的使一个节点到达应到的位置
int t = u;
if (2 * u <= mySize && h[t] > h[2 * u])
t = 2 * u;
if (2 * u + 1 <= mySize && h[t] > h[2 * u + 1])
t = 2 * u + 1;
if (t != u)
{
swap(h[u], h[t]); //下一层递归的入口
down(t);
}
}
up
对一个节点,如果它小于它的父节点,则应将其上升,即与父节点的位置互换,以满足堆的定义。
void up(int u) //此处未用递归,但可以用递归实现
{
while (u / 2)
{
if (h[u] >= h[u / 2])
break;
swap(u, u / 2);
u /= 2;
}
}
堆的初始化
给定一个元素集合,如何才将它变成一个堆:
从下标为mySize/2的元素开始,到下标为1的元素结束,分别执行一次down操作。
cin >> n;
mySize=n;
for (int i = 1; i <= n; i++)
cin >> h[i];
for (int i = n / 2; i >= 1; i--)
down(i);
对初始化的解释:
我们初始化就使要将原始的数据集合变成符合堆定义的数据集合。
二叉树的叶子节点没有孩子节点,因此必然满足定义中的方程,我们从最后一个不是叶子节点的节点开始逐个向前进行down操作,就可以使整棵二叉树满足定义变成堆。
堆的功能操作
对堆的功能操作有以下几种:
- 插入一个数
- 求堆中的最小值
- 删除任意一个数
- 修改任意一个数
插入
将其插在堆的末端,之后执行up操作。
int x;
cin >> x;
h[++mySize] = x;
up(mySize);
求最小值
最小值就是堆顶元素,即h[1]。
注意堆中元素下标从1开始,方便处理。
删除
将待删除元素与堆末端元素互换,mySize减一,再对交换过去的末端元素进行一次down操作,一次up操作(也可以判断该元素与父节点和子节点的关系具体选择一个操作,而直接一次up一次down就不用额外判断了)。
int x;
cin >> x;
swap(h[x], h[mySize--]);
up(x);
down(x);
修改
对某一元素修改后,执行一次down操作和一次up操作。
int k,x;
cin >> k >> x;
h[k] = x;
up(k);
down(k);
总结
对堆操作时,要时刻注意使堆中的元素满足堆定义中的方程,适时使用down和up操作。