堆排序
堆的结构
堆是一个完全二叉树,除了最后一个节点之外,上层的节点都是满的,最后一层节点从左到右依次排列
小根堆:每个点的值小于等于左右两个孩子,根节点为所有元素的最小值
大根堆:每个点的值大于等于左右两个孩子,根节点为所有元素的最大值
堆的存储方式
用一维数组存储
在标号从1到n的堆里,一个标号为i的节点,它的左孩子标号=2i,右孩子标号=2i+1
最后一个有孩子的节点标号为n/2,从这个点开始从后往前维护每个有孩子的节点堆的性质
堆的操作
down(x):往下调整,把某点的值变大了,则向下移
up(x):往上调整:把某点的值变小了,则向上移
1.插入一个数
heap[++size]=heapsize;up(size)//向上调整
2.求集合当中的最小值
heap[1]
3.删除最小值
heap[1]=heap[head];size–;dowm(1)//向下调整
4.删除任意一个元素
heap[k]=heap[size],size–;down(k),up(k)//两个会执行其中一个
5.修改任意一个元素
heap[k]=x;down(x),up(x);
堆的代码
维护堆的性质
向下维护小根堆
在一个小堆中,设当前小堆的根节点为小堆的最小值,然后依次与它的左孩子和右孩子比较,若根节点不是当前堆中最小的,则与有最小值的节点交换值,并维护被交换的孩子节点(因为可能在以被交换的孩子节点为父节点的小根堆中,其值不是最小值),但若在小根堆中没有发生元素交换(即根节点以为最小值)则不用向下维护了
void down(int x)
{
int min=x;//设当前节点即为改小根堆最小值
int l=x*2,r=x*2+1;//左孩子和右孩子节点编号
if(f[l]<f[min]&&l<=n)//若左孩子节点比当前节点小且左孩子没有越界
min=l;
if(f[r]<f[min]&&r<=n)//若右孩子节点比当前节点小且右孩子没有越界
min=r;
if(min!=x)//若交换了节点
{
swap(f[min],f[x]);//交换节点值
down(min);//向下维护交换了元素的节点
}
当将整个数组都构成小根堆后,其根节点(即数组下标为1的点)为整个数组的最小值,此时可以将其输出出来
而将它删除的操作则是把它与堆中最后一个数交换元素,并删除最后一个元素(做法是n–,即下次维护堆时不再考虑下标为n的节点,将它忽略掉)此时再从下标为1的点开始向下维护堆的性质
printf("%d ",f[1]);//输出最小值
f[1]=f[n];//交换第一个数与最后一个数的元素
n--;//删除最后一个数
down(1);//从下标为1的点开始向下维护
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int f[N];
int n,m,size;
void down(int x)
{
int min=x;//设当前节点即为改小根堆最小值
int l=x*2,r=x*2+1;//左孩子和右孩子节点编号
if(f[l]<f[min]&&l<=n)//若左孩子节点比当前节点小且左孩子没有越界 (1)注意范围
min=l;
if(f[r]<f[min]&&r<=n)//若右孩子节点比当前节点小且右孩子没有越界
min=r;
if(min!=x)//若交换了节点
{
swap(f[min],f[x]);//交换节点值
down(min);//向下维护交换了元素的节点
}
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
scanf("%d",&f[i]);
for(int i=n/2;i>=1;i--)
{
down(i);
}
//此时已做成小根堆
//此时f[1]为整个数组中元素最小的点
//输出最小的点f[1],与最后一个节点交换
while(m--)
{
printf("%d ",f[1]);//输出最小值
f[1]=f[n];//交换第一个数与最后一个数的元素
n--;//删除最后一个数
down(1);//从下标为1的点开始向下维护
}
return 0;
}
补充
up代码
void up(int n)
{
while(n/2&&f[n/2]>f[n])
{
swap(f[n/2],f[n]);
n/=2;
}
}