堆排序
2025-03-02 11:38:04
发布于：北京
#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;
}
全部评论 36
![]#include<bits/stdc++.h>
using namespace std;
int s[10005], n, k;
bool cmp(int x, int y) {
return x > y;
}
int main() {
sort(s + 1, s + n + 1); //升 优先级
sort(s + 1, s + n + 1, cmp); //降
//数组下标 x -- y 排序
int x, y;
sort(s + x, s + y + 1);//求第 k 大，第 k 小问题 //求第 k 大问题 sort(s + 1, s + n + 1, cmp); cout << s[k]; //求第 k 小问题 sort(s + 1, s + n + 1); cout << s[k]; //字符本质上是整数，可以比较 --> 可以排序 char cs[105] = "bca"; sort(cs + 0, cs + 3); //string 字符串可以通过 >、<、>=、<=、==、!=进行字典序比较,所以也可以进行排序 string ss[105] = {"abc", "bcd", "aaa"}; sort(ss + 0, ss + 3); //排序去重 sort(s + 1, s + n + 1); int c[105], l = 0; c[++l] = s[1]; for (int i = 2; i <= n; i++) { if (s[i] != s[i - 1]) { c[++l] = s[i]; } } for (int i = 1; i <= l; i++) { cout << c[i] << " "; } //最小差值问题 //排完序后，最小差值只可能是两个相邻元素的差值 sort(s + 1, s + n + 1); int minn = 2e9; for (int i = 1; i < n; i++) { if(minn > s[i+1] - s[i]){ minn = s[i+1] - s[i]; } } return 0;}
2025-03-02 来自 北京
0#include<bits/stdc++.h>
using namespace std;
int heap[100005];
int heap_size=0;
void put(int d){
int son,pa;
heap[++heap_size]=d;
son=heap_size;
while(son>1){
pa=son>>1;
if(heap[son]>=heap[pa]){
break;
}
swap(heap[son],heap[pa]);
son=pa;
}
}
int main(){return 0;}
2025-03-02 来自 北京
0#include<bits/stdc++.h>
using namespace std;
int heap[100005];
int heap_size=0;
void put(int d){
int son,pa;
heap[++heap_size]=d;
son=heap_size;
while(son>1){
pa=son>>1;
if(heap[son]>=heap[pa]){
break;
}
swap(heap[son],heap[pa]);
son=pa;
}
}
int main(){return 0;}
2025-03-02 来自 北京
0#include<bits/stdc++.h>
using namespace std;
int heap[100005];
int heap_size=0;
void put(int d){
int son,pa;
heap[++heap_size]=d;
son=heap_size;
while(son>1){
pa=son>>1;
if(heap[son]>=heap[pa]){
break;
}
swap(heap[son],heap[pa]);
son=pa;
}
}
int main(){return 0;}
2025-03-02 来自 北京
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;
}2025-03-02 来自 北京
0
有帮助，赞一个