文章目录
-
- 0. 前言
- 1. 堆排序
0. 前言
Biu
堆排序是一个不稳定的排序算法,对数据不敏感,时间复杂度稳定,主要分为两部分:建堆、堆排序。
其中建堆的时间复杂度是 O ( n ) O(n) O(n) 的,而排序选出一个最大、最小值的过程是 O ( l o g n ) O(logn) O(logn) 的,一共需要 n
次操作,故总共的时间复杂度是 O ( n l o g n ) O(nlogn) O(nlogn) 的。
堆主要的两个操作,在此仅使用向下调整 down()
操作即可,至于另一个注意点就是堆排序的建堆时间复杂度计算了,和树的高度密切相关,通过数学式子可以严格证明它是 O ( n ) O(n) O(n) 的时间复杂度。
1. 堆排序
代码:
#include <iostream>
using namespace std;
const int N = 1e5+5;
int n, m;
int h[N], tt;
void down(int u) {
int t = u; // t表示三个数中最小值编号
if (u * 2 <= tt && h[u * 2] < h[t]) t = u * 2; // 如果有左儿子并且左儿子比它小更新为左儿子
if (u * 2 + 1 <= tt && h[u * 2 + 1] < h[t]) t = u * 2 + 1;
if (u != t) swap(h[u], h[t]), down(t); // 当前根节点不是最小的,交换一下,递归处理即可
}
void up(int u) {
while (u / 2 && h[u / 2] > h[u]) swap(h[u], h[u / 2]), u /= 2;
}
int main() {
cin >> n >> m;
for (int i = 1; i <= n; ++i) cin >> h[i];
tt = n;
// 递归的O(n)建堆,时间不是O(logn)注意
// 从倒数第二层开始down,保证当前节点的左右儿子已经是堆了
for (int i = n / 2; i; --i) down(i);
while (m --) {
cout << h[1] << ' ';
h[1] = h[tt];
tt--;
down(1);
}
return 0;
}
今天的文章堆排序过程图解_小顶堆排序怎么排分享到此就结束了,感谢您的阅读,如果确实帮到您,您可以动动手指转发给其他人。
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
如需转载请保留出处:https://bianchenghao.cn/59081.html