堆排序
2025-03-02 11:38:04
发布于：北京
76阅读
0回复
0点赞
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 9;
int heap[maxn], heap_size;
void put(int d) {
int son, pa;
heap[++heap_size] = d;//新增一个结点，值为d
son = heap_size;
while (son > 1) { //向上调整，使其满足大根堆的性质
pa = son >> 1; //找到父节点
if (heap[son] <= heap[pa]) break; //如果父节点的值大于等于儿子结点，调整完毕
swap(heap[son], heap[pa]); //向上调整
son = pa;
}
}
//返回堆顶的值，并删除堆顶
int get() {
int pa, son, res;
res = heap[1]; //存储堆顶的值
heap[1] = heap[heap_size--]; //用最后一个元素覆盖堆顶，并把堆元素个数减一
pa = 1;
//向下调整
while (pa * 2 <= heap_size) {
son = pa * 2;
if (son < heap_size && heap[son + 1] > heap[son]) son++;//找到存在的儿子中最大的一个
if (heap[pa] >= heap[son]) break; //调整完毕
swap(heap[pa], heap[son]);//向下调整
pa = son;
}
return res;//返回堆顶的值
}
int main() {
int n;
cin >> n;
for (int i = 1; i <= n; i++) {
int x;
cin >> x;
put(x);
}
while (heap_size) {
cout << get() << " ";
}
return 0;
}
全部评论 48
https://xmcdn.oss-cn-shanghai.aliyuncs.com/cpp_community/images/sticker/emoji/%E4%B9%A6%E5%91%86%E5%AD%90.png
2025-05-18 来自 北京
0
有帮助，赞一个