大佬的堆排序详

堆排序

void HeapSort(vector<int>& arr)
{
    //构建大顶堆，非叶子节点个数
    for (int i = arr.size() / 2 - 1; i >= 0; i--)
    {
        //从第一个非叶子结点从下至上，从右至左调整结构
        AdjustHeap(arr, i, arr.size());
    }

    //每次把堆顶元素与末尾元素进行交换，获取一个最大的，然后继续调整堆
    for (int j = arr.size()-1; j > 0; j--)
    {
        SwapNum(arr, 0, j);
        AdjustHeap(arr, 0, j);
    }
}

void AdjustHeap(vector<int>& arr, int i, int length)
{
    int temp = arr[i];//先取出当前元素i
    for (int k = i * 2 + 1; k < length; k = k * 2 + 1)
    {
        //如果节点i的下面两个子节点中最大的比其大，则交换

        //让k指向2个中最小的子节点
        if (k + 1 < length && arr[k] > arr[k + 1])
            k++;

        //交换
        if (arr[k] < temp)
        {
            arr[i] = arr[k];
            i = k;
        }
        else
        {
            break;
        }
    }
    arr[i] = temp;
}

void SwapNum(vector<int>& arr, int a, int b)
{
    int temp = arr[a];
    arr[a] = arr[b];
    arr[b] = temp;
}

堆排序LeetCode题

https://leetcode-cn.com/problems/smallest-k-lcci/