堆的基本概念以及操作
概念
1.堆:本质上是特殊的完全二叉树
2.最小堆:每个父节点小于子女节点
最大堆:每个父节点大于子女节点
堆的存储
用一个一维数组来存
h[1]:根节点
h[x]:第x个节点
h[2*x]:第x个节点的左孩子
h[2*x+1]:第x个节点的右孩子
堆的创建(时间复杂度为O(n))
for(int i=n/2;i;i--) down(i);
- 证明
k层满二叉树,有2^k-1个节点
(2^k-1)/2,就成了从倒数第二层,最后一个节点开始
向下调整(因为最后一层没法向下调整了)
但是堆是k层完全二叉树,最后一层可能节点没满,假设有n个节点
n/2,代表非叶子节点的最后一个,从这个节点向下调整
也就是说,每次n/2 就调整非叶子节点上一层的节点
考虑O(n)
倒数第二层:有n/4 个节点 down (n/4)*1次
倒数第三层:有n/8 个节点 down (n/8)*2次
倒数第四层:有n/16个节点 down (n/16)*3次
....
求和之后S<n
手写堆的操作
- 插入一个数
h[++size]=x; //将x插入最后一个节点位置
up(size); //递归向上调整
- 求集合中的最小值
h[1]; //输出最小堆堆顶
- 删除最小值
h[1]=h[size]; //用最后一个节点的值覆盖堆顶
size--; //删除一个节点
down(1); //递归向下调整
- 删除任意一个元素
h[k]=h[size]; //用最后一个节点的值覆盖待删除节点
size--;
down(k); //因为不知道覆盖了是大还是小,这两个只可以执行一个,在函数体里面有判断
up(k); //这里为了减少代码量,就全写上
- 修改任意一个元素
h[k]=x;
down(k);
up(k);
堆排序
题目
输入一个长度为 n 的整数数列,从小到大输出前 m 小的数。
代码
#include <iostream>
#include <algorithm>
using namespace std;
const int N=1e5+10;
int h[N],Size;
int n,m;
void down(int u)
{
//t是父节点 两个孩子节点 数值最小的节点下标
int t=u;
if(2*u<=Size && h[t]>h[2*u]) t=2*u;
if(2*u+1<=Size && h[t]>h[2*u+1]) t=2*u+1;
//写h[t],不能写h[u]
// 因为得找出 某一结点中 左右子结点最小的那个。
//换成t的话,可以看做,结点,左子结点,右子结点,三者都互相比较后,得出了最小的点。
//如果不换,只能看作,求出一个比结点小的子结点,但却不一定是最小的。
if(t!=u) //最小值不是根节点
{
swap(h[u],h[t]);
down(t);
}
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) scanf("%d",&h[i]);
Size=n;
//构建最小堆
for(int i=n/2;i;i--) down(i);
while(m--)
{
//输出堆顶
cout<<h[1]<<" ";
//删除堆顶,重新构建最小堆
h[1]=h[Size];
Size--;
down(1);
//因为每次堆顶都是整个集合最小的数字,所以,每次输出堆顶都是最小的,即实现了堆排序
}
return 0;
}
模拟堆
最难的地方ph[]与hp[]
1.ph[k]:第k个插入的数,在堆中的下标是几? ph[k]=i;
2.hp[i]: 堆中下标为i的数,是第几个插入的数? hp[i]=k;
- 先把h[a]和h[b]交换
swap(h[a],h[b]);
-
堆中下标为a的数是第i个插入的数即hp[a]=i ph[i]=a
-
堆中下标为b的数是第j个插入的数即hp[b]=j ph[j]=b
-
由于二者要交换,所以需要让ph[i]=b;让ph[j]=a;
-
即第i个插入的数下标成了b
-
第j个插入的数下标成了a
swap(ph[hp[a]],ph[hp[b]])
-
但是此时 下标为a的数是第j个插入的数
-
下标为b的数是第i个插入的数
-
需要再交换一下hp
swap(hp[a],hp[b]);
模拟堆
#include<iostream>
#include<algorithm>
#include<string.h>
using namespace std;
const int N=1e5+10;
//sz存当前堆中元素的个数
//hp[k] 第k个插入的数在堆中的下标是几 i
//ph[i] 堆中下标为i的数是第几个插入的数 k
int h[N],ph[N],hp[N],sz;
void heap_swap(int a,int b)
{
swap(h[a],h[b]);
swap(ph[hp[a]],ph[hp[b]]);
swap(hp[a],hp[b]);
}
void down(int u)
{
int t=u;
if(2*u<=sz && h[t]>h[2*u]) t=2*u;
if(2*u+1<=sz && h[t]>h[2*u+1]) t=2*u+1;
if(t!=u)
{
heap_swap(t,u);
down(t);
}
}
void up(int u)
{
//t用来存父节点和一个孩子节点中值较大的那个
int t=u;
if(u/2 && h[t]<h[u/2]) t=u/2;
if(t!=u)
{
heap_swap(t,u);
up(t);
}
}
int main()
{
int n;
int m=0;
//sz存当前堆中元素的个数 m是第m个插入的数
scanf("%d",&n);
while (n--)
{
char op[10];int k,x;
scanf("%s",op);
//插入x
if(!strcmp(op,"I")) //字符串匹配 匹配返回0
{
scanf("%d",&x);
sz++;
m++;
h[sz]=x;
ph[m]=sz,hp[sz]=m;
up(sz);
}
//输出最小值
else if(!strcmp(op,"PM")) cout<<h[1]<<endl;
//删除最小值
else if(!strcmp(op,"DM"))
{
heap_swap(1,sz);
sz--;
down(1);
}
//删除第k个插入的数
else if(!strcmp(op,"D"))
{
scanf("%d",&k);
k=ph[k];
heap_swap(k,sz);
sz--;
down(k), up(k);
}
// else if(!strcmp(op,"D"))
// {
// scanf("%d",&k);
// heap_swap(ph[k],sz);
// sz--;
// down(ph[k]), up(p[k]); //这样写是错的,因为这里ph[k] 已经指向了最后并且sz-- 删除了
// }
//修改第k个插入的数
else if(!strcmp(op,"C"))
{
scanf("%d%d",&k,&x);
k=ph[k]; //取得第k个插入的数在堆中的下标
h[k]=x;
down(k),up(k);
}
}
return 0;
}