堆
堆通常是一个可以被看做一棵树的数组对象。堆总是满足下列性质:
- 堆总是一棵完全二叉树。
- 堆中某个节点的值总是不大于或不小于其父节点的值;
将根节点最大的堆叫做最大堆或大根堆,根节点最小的堆叫做最小堆或小根堆。常见的堆有二叉堆、斐波那契堆 等。
这里主要介绍二叉堆
二叉堆的储存
上面是逻辑上结构, 下面则是实际的储存结构,我将数组和树的都从1开始编号。
以下标pos为5,即值为4的点为例
pos的父亲节点为 pos>>1 = 2, 值为3, 左儿子节点为 pos<<1 = 10 值为 10, 右儿子节点为 pos<<1|1 = 11 值为 9
这图就是一个小根堆,大根堆也就容易理解了
栗子
题目很简单,用优先队列就能过。优先队列本质还是用堆实现的。
那我们还是用堆来实现。
根据题目要求,我们使用小根堆显然比较合适些;
//操作1 x,就将x放入数组的末尾
/*
dui[]数组用于储存堆元素
x 是要插入的元素
因为是向上更新的,所以函数名为 up
*/
void up(int x){
dui[++len] = x;
int pos = len;
while(pos > 1){ //位置是1的话, 即根节点,就没必要更新了
int fr = pos>>1; //父亲节点的位置
if(dui[pos] < dui[fr]) //要是小于父亲节点,就交换
swap(dui[pos], dui[fr]);
else
break;
pos>>=1;//交换后位置更新
}
}
/*
这样,就能保证每次插入新的元素之后,dui[1] 是堆中的最小值
*/
操作 2
就直接输出 dui[1] 就好了
//操作3 移除最小的元素
/*
如果只是单纯的移除掉根节点,肯定是不行的
所以,我们就把 dui[] 数组的最后一个元素覆盖掉 根节点 ,同时还要对堆进行维护, 使之依然是 小根堆
*/
void down(){
int pos = 1;
dui[1] = dui[len--]; //覆盖
while(pos<<1 <= len){ //保证有左子节点
int l = pos<<1, r = pos<<1|1, minn = l; //minn 用于记录左右子节点中最小的
if(r<=len && dui[r] < dui[l]) //在右子节点存在的情况下, 求出左右子节点中最小的
minn++;
if(dui[pos] > dui[minn]){ //更新维护
swap(dui[pos], dui[minn]);
pos = minn;
}
else
break;
}
}
本来想上图的,不过自己画的真的丑,自己随便模拟下就可以了
这样这个题目就能很轻松了水过去了
堆排序
堆排序就简单了啊,就是上面两个函数的结合啊。
上面的 操作1 就相当于 输入元素。
操作3 就不是覆盖了,是将 根节点 和 最后一个节 点交换了。
#include <bits/stdc++.h>
const int maxn = 100005;
using namespace std;
typedef long long ll;
int dui[maxn], len; // len 堆的实际长度
void up(int pos){
while(pos > 1){
int fr = pos>>1;
if(dui[pos] > dui[fr])
swap(dui[pos], dui[fr]);
else
break;
pos>>=1;
}
}
void down(int pos){
while(pos<<1 <= len){
int l = pos<<1, r = pos<<1|1, minn = l;
if(r<=len && dui[r]>dui[l])
minn++;
if(dui[pos] < dui[minn]){
swap(dui[pos], dui[minn]);
pos = minn;
}
else
break;
}
}
int main()
{
int n; //要排序的数组的长度
scanf("%d", &n);
len = n;
for(int i=1; i<=n; i++){
scanf("%d", &dui[i]);
up(i); //每次输入即插入, 要更新
}
for(int i=1; i<n; i++){
swap(dui[1], dui[len]); // 根节点 和 最后一个节 点交换
len--;
down(1); //更新
}
for(int i=1; i<=n; i++)
printf("%d ", dui[i]);
return 0;
}
上面是利用小根堆, 将数组按降序排列
升序怎么办??
数组倒着输出就好了啊
还有大根堆啊