--- title: "堆排序" created: 2025-11-28 tags: - 算法 --- # 堆排序 ## 题目 [堆排序](https://www.acwing.com/problem/content/840/) ![[image-3b08aeab.png]] ## 思路分析 堆中的一系列操作其实就是变相的使用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) 怎么得来就不管了 ## 代码实现 ```cpp #include 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<