1. 原理

最大/最小堆的堆顶元素是整个数据集的最大/最小值。利用这个性质，可以首先取得堆顶元素作为有序序列的第一个元素，然后把剩余元素调整成堆，再取出堆顶元素放到有序序列的第二个位置，以此类推，就可以得到一个有序序列。

根据这种介绍可以看出得到升序序列需要最大堆，降序序列需要最小堆。

2. 代码

typedef int(*Compare)(int x, int y);  // 通过回调函数直接控制排出的是升序还是降序

// call back
int Greater(int x, int y);
int Less(int x, int y);

void AdjustDown(int* arr, int size, int root, Compare compare) {
    int parent = root;
    int child = parent * 2 + 1;

    while (child < size) {
        if (child + 1 < size && compare(arr[child + 1], arr[child])) {
            child++;
        }

        if (compare(arr[child], arr[parent])) {
            Swap(&arr[child], &arr[parent]);
            parent = child;
            child = parent * 2 + 1;
        }
        else {
            break;
        }
    }
}

void HeapSort(int* arr, int size, Compare compare) {
    if (size == 1) {
        return;
    }

    // 1. 建堆
    int index = (size - 1) / 2;
    while (index >= 0) {
        // 向下调整
        AdjustDown(arr, size, index, compare);
        index--;
    }

    // 2. 排序
    int end = size - 1;
    Swap(&arr[0], &arr[end--]);
    while (end) {
        // 向下调整
        AdjustDown(arr, end + 1, 0, compare);

        Swap(&arr[0], &arr[end--]);
    }
}