题目一：推排序
838. 堆排序 - AcWing题库
分析
代码
优先队列，sort 也能解。
#include<bits/stdc++.h>
using namespace std;const int N = 1e5+10;
int h[N], idx;int n, m;void down(int u) {int t = u;// 根、左孩子、右孩子中最小值,然后和根交换值if(2*u<=idx && h[t] > h[u*2]) t = 2*u;if(2*u+1<=idx && h[t] > h[u*2+1]) t = u*2+1;if(u != t) {swap(h[u],h[t]);down(t);}
}int main() {cin >> n >> m;for(int i = 1; i <= n; i ++) cin >> h[i];idx = n;// 建堆for(int i = n/2; i > 0; i --) down(i);while(m --) {cout << h[1] << " ";h[1] = h[idx--];down(1);}return 0;
}题目二、模拟堆
839. 模拟堆 - AcWing题库
分析
代码
#include<bits/stdc++.h>
using namespace std;const int N = 1e5+10;int h[N], idx;
int hp[N], ph[N], num;// a b 是完全二叉树中对应位置
void heap_swap(int a, int b) {swap(ph[hp[a]],ph[hp[b]]);swap(hp[a],hp[b]);swap(h[a],h[b]);
}
// 向下，两分枝最小值交换，大则向下/三者比较
void down(int u) {int t = u;if(2*u <= idx && h[t] > h[2*u]) t = 2*u;if(2*u+1 <= idx && h[t] > h[2*u+1]) t = 2*u+1;if(u!=t) {heap_swap(t,u);down(t);}
}
// 小则向上，两比较
void up(int u) {while(u/2>0 && h[u/2] > h[u]) {heap_swap(u/2,u);u /= 2; }
}int main() {int _;cin >> _;while(_ --) {int k, x;char op[3];cin >> op;//用string也可以，用 char* 的比较函数也行strcmp// 插入xif(!strcmp(op,"I")) {cin >> x;idx ++, num ++;ph[num] = idx, hp[idx] = num;h[idx] = x;up(idx);}//输出min (堆顶)else if(!strcmp(op,"PM")) cout << h[1] << endl;//删除minelse if(!strcmp(op,"DM")) {heap_swap(1,idx);idx --;down(1);}// 删除第k个插入的值else if(!strcmp(op,"D")) {cin >> k;k = ph[k];heap_swap(k,idx);idx --;down(k); up(k);}// 修改第k个插入的值为xelse if(!strcmp(op,"C")) {cin >> k >> x;k = ph[k];h[k] = x;down(k), up(k);}}return 0;
}
