from -> introdution to algorithms
大体和堆差不多。贴个代码
#include <stdio.h>
#include <string.h>
int a[100], heapsize, n;
int parent(int i){
return i / 2;
}
int left(int i){
return i * 2;
}
int right(int i){
return i * 2 + 1;
}
void heapfy(int i){
int largest = i, l = left(i), r = right(i), t;
if(l <= heapsize && a[l] > a[i])largest = l;
if(r <= heapsize && a[largest] < a[r])largest = r;
if(largest != i){
t = a[i];
a[i] = a[largest];
a[largest] = t;
heapfy(largest);
}
}
void push(){ //插入的节点直接放到叶子上就可以，然后heapsize++， 再沿根向上，保持堆的性质。
int i = ++heapsize, t;
while(i > 1 && a[parent(i)] < a[i]){
t = a[i];
a[i] = a[parent(i)];
a[parent(i)] = t;
i = parent(i);
}
}
void pop(){
int t;
t = a[1];
a[1] = a[heapsize];
a[heapsize] = t;
heapsize--;
heapfy(1);
}
int pqmax(){
return a[1];
}
int main(){
freopen("pq.in", "r", stdin);
freopen("pq.out", "w", stdout);
int i, j, k;
while(scanf("%d", &n) != -1){
heapsize = 0;
for(i = 1; i <= n; i++){
scanf("%d", &a[i]);
push();
}
while(heapsize >= 1){
printf("%d ", pqmax());
pop();
}puts("");
}
return 0;
}