堆排序
题目 堆排序
思路分析
堆中的一系列操作其实就是变相的使用down、up进行调整
比如
插入一个数
就在堆的最后一个位置（数组的可用位置处）加上一个x
heap[++size]=x;
然后不断对它进行调整 up(size);
即可
求集合当中的最小值
其实就是堆形成后的堆顶元素
heap[1];
删除第一个元素
考虑两个问题
删除后 堆可能就发生了变化可能性质就没满足 需要调整
其二 用的是数组存储 删除元素当然还是删末尾的容易 这样无需挪动元素
所以 把最后一个元素 替换掉第一个元素 然后size–
把最后一个元素删掉 再不断对这个n挪上来的元素进行down调整
heap[1]=heap[size];
size–;
down(1);
删除任意一个元素
同理
把最后一个元素挪过来 但是这里情况有点不一样 它可能往上调整也可能往下调整
不像前面一定是向下调整 所以可能还需要判断一下是进行up还是down
实际可以不用 因为down up内部都是有判断的
所以完全可以直接调用两个 它自己会选择一个进去
heap[k]=heap[size];
size–;
down[k];
up[k];//只会执行一个
修改任意一个元素
heap[k]=x;
down[k];
up[k];
核心就在于down up如何实现
down 对于每一个结点 看是否有左右孩子 并在这三个点中找到最值 找到到后交换位置进行调整 然后递归该操作直到调整完成
up 对于每个结点 看是否存在父结点 同理判断是否需要调整 也是递归该操作直到调整完成
还有一个注意的点就是 对于堆的构造
其实也是不断调整的一个过程
先随意将无需的序列存入数组中
然后不断进行调整就行了 最后会得到一个小(大)根堆
这个调整有个注意的点是 从n/2开始调整（n为最后一层的点 没有孩子了 而n/2是倒数第二层 是最底的有孩子的结点 从n/2开始往前遍历 就可以考虑调整到所有的点）
for(int i=n/2;i;i–)
down(i);
且这样的话 时间复杂度能缩减到O(n) 怎么得来就不管了
代码实现
#include<bits/stdc++.h>
using namespace std;
const int N=100010;
int h[N];
int mysize;
void down(int x)
{
int t=x;//t保存最小值 初始化为传入的值 去与孩子比较 考虑替换
if(2*x<=mysize && h[t]>h[2*x])//如果左孩子存在 且更小
t=2*x;
if(2*x+1<=mysize && h[t]>h[2*x+1])//如果右孩子存在 且更小
t=2*x+1;
if(x!=t)//不是自身则表示需要调整
{
swap(h[x],h[t]);
down(t);//递归继续向下调整
}
}
int main()
{
int n,m;
cin>>n>>m;
mysize=n;
//建堆其实也就是一个调整的过程
//先不管那么多直接把无序的数存进来 经过一系列调整后就会变成小根堆
for(int i=1;i<=n;i++)
scanf("%d",&h[i]);
//调整为堆
for(int i=n/2;i;i--)
{
//n是最大值，n/2是n的父节点
//因为n是最大，所以n/2是最大的有子节点的父节点
//所以从n/2往前遍历，就可以把整个数组遍历一遍
down(i);
}
while(m--)
{//输出就直接把最顶上取出再删掉继续调整 永远是最小在顶上
cout<<h[1]<<" ";
h[1]=h[mysize--];
down(1);
}
return 0;
}
💬 评论