重写的标题：小顶堆算法在堆排序中的应用

• 使用小顶堆算法。则要保持堆的个数为k个，将前k个大的数据保存到堆里。堆顶保存较小的，使用小顶堆就可以获取到第k大的数

void Swap(int *arr, int i, int j)
{
    int tmp = arr[i];
    arr[i] = arr[j];
    arr[j] = tmp;
}
void SiftUp(int *arr, int i)
{
    if (i == 0) return;
    int parent = (i + 1) / 2 - 1;
    if (i != parent) {
        if (arr[i] < arr[parent]) {
            Swap(arr, i, parent);
            SiftUp(arr, parent);
        }
    }
}
void AdjustHeap(int *arr, int i, int arrSize)
{
    int left = 2 * i + 1;
    int right = 2 * i + 2;
    int min = i;
    if (left < arrSize && arr[left] < arr[i]) {
        min = left;
    }
    if (right < arrSize && arr[right] < arr[min]) {
        min = right;
    }
    if (i != min) {
        Swap(arr, i, min);
        AdjustHeap(arr, min, arrSize);
    }
}

int findKthLargest(int* arr, int numsSize, int k)
{
    // 首先将数组总的前k个数按照最小堆排序
    for (int i = 0; i < k; i++) {
        SiftUp(arr, i);
    }
    // 然后将剩下的元素，添加到最小堆里
    // 要求堆的个数保持k个不变，如果新的数值比堆顶还小，则直接跳过，反正，将堆顶替换之，然后调整堆的状态。
    for (int i = k; i < numsSize; i++) {
        if (arr[0] >= arr[i]) {
            continue;
        }
        arr[0] = arr[i];
        AdjustHeap(arr, 0, k);
    }
    return arr[0];
}

有必要总结一个大小顶堆的通用模版

void Swap(int *arr, int i, int j)
{
    int tmp = arr[i];
    arr[i] = arr[j];
    arr[j] = tmp;
}
typedef int (MyCmp)(const void *a, const void *b);
// 小顶堆
int HeapCmp(const void *a, const void *b)
{
    int left = *(int *)a;
    int right = *(int *)b;
    return left < right ? -1 : 1;
}

• 上浮函数，入参cmp函数

void SiftUp(int *arr, int i, MyCmp cmp)
{
    if (i == 0) return;
    int parent = (i + 1) / 2 - 1;
    if (i != parent) {
        if (cmp(&arr[parent], &arr[i]) > 0) { //  if (arr[parent] > arr[i]) {
            Swap(arr, i, parent);
            SiftUp(arr, parent, cmp);
        }
    }
}

• 重新调整堆属性，函数，入参cmp函数

void AdjustHeap(int *arr, int i, int arrSize, MyCmp cmp)
{
    int left = 2 * i + 1;
    int right = 2 * i + 2;
    int min = i;
    // if (left < arrSize && arr[i] > arr[left]) {
    if (left < arrSize && cmp(&arr[i], &arr[left]) > 0) {
        min = left;
    }
    if (right < arrSize && cmp(&arr[min], &arr[right]) > 0) {
        min = right;
    }
    if (i != min) {
        Swap(arr, i, min);
        AdjustHeap(arr, min, arrSize, cmp);
    }
}

• 主函数

int findKthLargest(int* arr, int numsSize, int k)
{

    // 首先将数组总的前k个数按照最小堆排序
    for (int i = 0; i < k; i++) {
        SiftUp(arr, i, HeapCmp);
    }

    // 然后将剩下的元素，添加到最小堆里
    // 要求堆的个数保持k个不变，如果新的数值比堆顶还小，则直接跳过，反正，将堆顶替换之，然后调整堆的状态。
    for (int i = k; i < numsSize; i++) {
        if (arr[0] >= arr[i]) {
            continue;
        }
        arr[0] = arr[i];
        AdjustHeap(arr, 0, k, HeapCmp);
    }
    return arr[0];
}