#define PARENT(__i) (__i / 2) #define LEFT(__i) (__i * 2) #define RIGHT(__i) (__i * 2 + 1) int heap_size,length; /*inline*/void exchange(int *a,int *b) { *a ^= *b; *b = *a ^ *b; *a ^= *b; return; } void max_heapify(int A[],int i) { int l,r; int largest; l = LEFT(i); r = RIGHT(i); largest = (l <= heap_size && A[l] > A[i])? l: i; if(r <= heap_size && A[r] > A[largest]) largest = r; if(largest != i) { exchange(&A[i],&A[largest]); max_heapify(A,largest); } return; } void build_max_heap(int A[]) { int i; heap_size = length; for(i = length / 2;i > 0;i--) max_heapify(A,i); return; } void heapsort(int A[]) { int i; build_max_heap(A); for(i = length;i > 1;i--) { exchange(&A[1],&A[i]); heap_size--; max_heapify(A,1); } return; }