#include <stdio.h> void heapify(int* intp, unsigned idx, unsigned nr) { unsigned j = idx; while (1) { unsigned i = idx * 2 + 1; if (nr > i && intp[i] > intp[j]) { j = i; } ++i; if (nr > i && intp[i] > intp[j]) { j = i; } if (j == idx) { break; } int n = intp[idx]; intp[idx] = intp[j]; intp[j] = n; idx = j; } } void make_heap(int* intp, unsigned nr) { unsigned idx = (nr / 2 - 1); while (idx != (unsigned) (-1)) { heapify(intp, idx, nr); idx -= 1; } } void heap_sort(int* intp, unsigned nr) { do { --nr; int n = intp[0]; intp[0] = intp[nr]; intp[nr] = n; heapify(intp, 0, nr); } while (nr > 0); } int main(void) { int a[] = {6, 9, 2, 4, 0, 3, 8, 1, 5}; unsigned nr = sizeof(a) / sizeof(a[0]); if (nr > 0) { make_heap(a, nr); heap_sort(a, nr); for (int i = 0; i < nr; ++i) { printf("%d ", a[i]); } printf("\n"); } return 0; }