Đang tải…
Đang tải…
Xây max-heap rồi liên tục đưa gốc (lớn nhất) về cuối và khôi phục heap — tại chỗ và O(n log n) trong mọi trường hợp.
Xây dựng 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}