C++ 手动实现堆

在C++ STL中其实是有堆的实现的，C++ 中的priority_queue就是由堆实现的，但是在面试中堆排序还是非常常问的，所以还是非常有必要手动实现一下堆。

堆的定义

堆是一种特殊的完全二叉树，其满足以下两个条件：

1. 堆中任意节点的值总是不大于（或不小于）其子节点的值。
2. 堆总是一棵完全二叉树。

其中节点值不小于其子节点的堆称为大跟堆，节点值不大于其子节点的堆称为小跟堆。

堆的实现

void maxHeapify(vector<int> &nums, int idx, int n)     // 调整为大根堆
{
    int left = idx * 2, right = idx * 2 + 1, largest = idx;
    if(left < n && nums[left] > nums[largest])
    {
        largest = left;
    }
    if(right < n && nums[right] > nums[largest])
        largest = right;

    if(largest != idx)
    {
        swap(nums[idx], nums[largest]);
        maxHeapify(nums, largest, n);
    }
}

void buildMaxHeap(vector<int> &nums, int n)     // 建堆
{
    for(int idx = n / 2; idx > -1; --idx)
        maxHeapify(nums, idx, n);
}

这里初始给了一个数组，然后调用buildMaxHeap函数建堆，建堆的过程就是从最后一个非叶子节点开始，调用maxHeapify函数，将其调整为大根堆，然后再依次向前调整，直到根节点。

堆排序

// 将nums从小到大排序, 直接在原数组上排序，没有返回值
void findKthLargest(vector<int>& nums, int k) 
{
    int n = nums.size();
    buildMaxHeap(nums, n);
    while(n > 0)
    {
        swap(nums[0], nums[n - 1]);     // 弹出堆顶元素，并将堆大小-1，-1操作在下行
        maxHeapify(nums, 0, --n);       // 调整为大根堆
    }
}