#include <stdio.h> void exch(int& a, int &b) { int tmp = a; a = b; b = tmp; } void fixdown(int a[], int k, int N) { while(2*k <= N) { int j=k*2; if(j<N && a[j]<a[j+1]) j++; if(!(a[k]<a[j])) break; exch(a[k], a[j]); k = j; } } void heapsort(int a[], int l, int r) { int k, N=r-l+1; int *pq = a+l-1; //notice! for(k = N/2; k>=1; k--) fixdown(pq, k, N); while(N>1) { exch(pq[1], pq[N]); fixdown(pq, 1, --N); } } int main() { int a[10] = {3,5,4,8,6,9,6,5,4,1}; heapsort(a, 0, 9); for(int i=0; i<10; i++) printf("%d ", a[i]); printf("\n"); return 0; }