笔记
2026-05-15 17:59:51
发布于：北京
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10; // 堆最大长度
int heap[N]; // 堆数组
int heap_size = 0; // 堆当前元素个数
void put(int x){
heap_size ++;//堆里面的元素数量增加1个
heap[heap_size] = x;
int p = heap_size;//当前位置
while(p != 1 && heap[p] < heap[p/2]){//当前结点比父节点小
swap(heap[p], heap[p/2]);
p = p/2;
}
}
int get(){//删除堆顶，删除树根
int res = heap[1];//去掉堆顶
//最后一个元素补上空位置
heap[1] = heap[heap_size];
heap_size --;
//heap[1]可能比较大。将heap[1]往下挪动
int p = 1;
while(p2 <= heap_size){//必须保证当前结点有儿子
int minson = p2;//找出值最小的儿子编号
if(p2 + 1 <= heap_size){//如果有右儿子
if(heap[p2 + 1] < heap[p2]){
minson = p2 + 1;//最小的是右儿子
}
}
if(heap[p] > heap[minson]){//
swap(heap[p], heap[minson]);
p = minson;
}
else break;
}
return res;
}
int main() {
int n;
cin >> n;
// 插入n个数，构建小根堆
for (int i = 1; i <= n; i++) {
int x;
cin >> x;
put(x);
}
for (int i = 1; i <= n; i ++){
cout << heap[i] << ' ';
}
cout << endl;
return 0;
}
这里空空如也
有帮助，赞一个