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
| #include <stdio.h>
void heapify (int tree[], int n, int i){ if (i >= n) { return; } int max = i; int c1 = 2*i + 1; int c2 = 2*i + 2; if (c1 < n && tree[c1] > tree[max]) { max = c1; } if (c2 < n && tree[c2] > tree[max]) { max = c2; } if (max != i) { swap(tree, max, i); heapify(tree, n, max); } }
void build_heap (int tree[], int n) { int last_node = n - 1; int parent = (last_node-1)/2; int i; for (i = parent; i >= 0; i--) { heapify(tree, n, i); } }
void heap_sort (int tree[], int n) { build_heap(tree,n); int i; for (i = n-1; i >= 0; i--) { swap(tree, i, 0); heapify(tree, i, 0); } }
int main() { int tree[] = {10,6,5,4,1,3}; int n = 6; int i; for (i = 0; i < n; i++) { printf(“%d\n”,tree[i]); } return 0; }
|