堆排序

在堆排序算法中，我们使用的是最大堆。

void MaxHeapify(int *array, int n, int i)
{
    int left = 2 * i;
    int right = 2 * i + 1;
    
    int largest = i;
    if (left <= n && array[left] > array[largest])
        largest = left;
    if (right <= n && array[right] > array[largest])
        largest = right;
    
    if (largest != i) {
        std::swap(array[i], array[largest]);
        MaxHeapify(array, n, largest);
    }
}

void BuildMaxHeap(int *array, int n)
{
    for (int i = n / 2; i >= 1; i--) {
        MaxHeapify(array, n, i);
    }
}

void HeapSort(int *array, int n)
{
    BuildMaxHeap(array, n);
    for (int i = n; i >= 2; i--) {
        std::swap(array[1], array[i]);
        n--;
        MaxHeapify(array, n, 1);
    }
}