Loading…
Loading…
Builds a max-heap, then repeatedly swaps the root (largest) to the end and restores the heap — in-place and O(n log n) in every case.
Build a max-heap.
1void heapSort(int[] a) {2 int n = a.length;3 for (int i = n/2-1; i >= 0; i--) siftDown(a, i, n);4 for (int end = n-1; end > 0; end--) {5 int t = a[0]; a[0] = a[end]; a[end] = t;6 siftDown(a, 0, end);7 }8}9void siftDown(int[] a, int root, int end) {10 while (2*root+1 < end) {11 int c = 2*root+1;12 if (c+1 < end && a[c+1] > a[c]) c++;13 if (a[root] >= a[c]) break;14 int t=a[root]; a[root]=a[c]; a[c]=t; root=c;15 }16}