含注解代码
#include <stdio.h>
const int N = 1e5 + 10;
int h[N], size;
int swap(int &a, int &b) { int tmp = a; a = b; b = tmp; }
void down(int u){
int t = u;
// 找到u、u*2和u*2 + 1中最小的那个元素
if (u * 2 <= size && h[u * 2] < h[t]) t = u * 2;
if (u * 2 + 1 <= size && h[u * 2 + 1] < h[t]) t = u * 2 + 1;
if(t != u){ // 若根结点不是最小的元素,则与其最小的元素进行交换
swap(h[u], h[t]);
down(t);
}
}
void up(int u){
while(u / 2 && h[u / 2] > h[u]){
swap(h[u / 2], h[u]);
u /= 2;
}
}
int main(){
int n, m; scanf("%d%d", &n, &m);
for(int i = 1; i <= n; i++) scanf("%d", &h[i]);
size = n;
// 建堆,用此方法可将时间复杂度从O(nlog n)优化至O(n)
for(int i = n / 2; i; i--) down(i); // 从倒数第二层开始建堆,由下至上递归,可保证下方的树均为建好的树
//for(int i = 1; i <= n; i++) up(i);
while(m--){
printf("%d ", h[1]); // 输出堆顶元素
h[1] = h[size--]; // 将树中最后一个结点覆盖根结点
down(1); // 调整堆
}
return 0;
}
无注解代码
#include <stdio.h>
const int N = 1e5 + 10;
int heap[N], size;
void swap(int &a, int &b) { int tmp = a; a = b; b = tmp; }
void down(int u){
int t = u;
if(u * 2 <= size && heap[u * 2] < heap[t]) t = u * 2;
if(u * 2 + 1 <= size && heap[u * 2 + 1] < heap[t]) t = u * 2 + 1;
if(u != t){
swap(heap[u], heap[t]);
down(t);
}
}
void up(int u){
while(u / 2 > 0 && heap[u / 2] > heap[u]){
swap(heap[u / 2], heap[u]);
u /= 2;
}
}
int main(){
int n, m; scanf("%d%d", &n, &m);
for(int i = 1; i <= n; i++) scanf("%d", &heap[i]);
size = n;
for(int i = n / 2; i; i--) down(i);
//for(int i = 1; i <= n; i++) up(i);
while(m--){
printf("%d ", heap[1]);
heap[1] = heap[size--];
down(1);
}
return 0;
}