1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74
| #include <stdio.h>
void print_list(int *ar, int n) { int i; printf("[ "); for (i=0; i<n; i++) { printf("%d ", ar[i]); } printf("]\n");
} static void heapify(int *ar, int idx, int max) { int left = 2*idx + 1; int right = 2*idx +2; int largest;
if (left < max && ar[left] > ar[idx]) { largest = left; } else { largest = idx; }
if (right < max && ar[right] > ar[largest]) { largest = right; }
if (largest != idx) { int tmp; tmp = ar[idx]; ar[idx] = ar[largest]; ar[largest] = tmp;
heapify(ar, largest, max); } }
static void buildHeap(int *ar, int n) { int i; for (i=n/2-1; i>=0; i--) { heapify(ar, i, n); } }
void heap_sort(int *ar, int n) { int i; int tmp; buildHeap(ar, n); printf("build:"); for (i=n-1; i>=1; i--) { tmp = ar[0]; ar[0] = ar[i]; ar[i] = tmp;
heapify(ar, 0, i); } }
int main(int argc, char *argv[]) { int a[] = {5, 3, 16, 2, 10, 14}; int len=sizeof(a)/sizeof(int); printf("begin: "); print_list(a, len); heap_sort(a, len); printf("end "); print_list(a, len); return 0; }
|