堆排序【Heap Sort】

#include <iostream>
#include <algorithm>
using namespace std;
void MaxHeapify(int heap[], int root, int tail) {
    int p = root;
    int lch = p * 2 + 1;
    while (lch <= tail) {
        if (lch + 1 <= tail && heap[lch] < heap[lch + 1])
            lch++;
        if (heap[p] > heap[lch])
            return;
        else {
            std::swap(heap[p], heap[lch]);
            p = lch;
            lch = p * 2 + 1;
        }
    }
}
void HeapSort(int heap[], int sz) {
    // 从最后一个父节点(sz / 2 - 1)开始调整
    for (int i = sz / 2 - 1; i >= 0; --i)
        MaxHeapify(heap, i, sz - 1);
    /*由于堆也是用数组模拟的，故堆化数组后，第一次将A[0]与A[n - 1]交换，再对A[0…n-2]重新恢复堆。
    第二次将A[0]与A[n – 2]交换，再对A[0…n - 3]重新恢复堆，重复这样的操作直到A[0]与A[1]交换。
    由于每次都是将最小的数据并入到后面的有序区间，故操作完成后整个数组就有序了。有点类似于直接选择排序。*/
    for (int i = sz - 1; i > 0; --i) {
        std::swap(heap[0], heap[i]);
        MaxHeapify(heap, 0, i - 1);
    }
}
int main() {
    int Heap[] = { 3,2,6,7,4,5,9,8,1 };
    int sz = (int)sizeof(Heap) / sizeof(*Heap);
    HeapSort(Heap, sz);
    for (int i = 0; i < sz; ++i)
        std::cout << Heap[i] << ‘ ‘;
    return 0;
}