03 堆

堆

堆是每个节点都大于/小于其父节点的树。二叉堆是一棵完全二叉树。

操作

插入元素时，将新元素插入到最后一层的最右侧（或新建一层）；此后，不断与其父节点比较并更新。

删除时，将堆顶元素与最后一个元素交换，删除堆顶元素；此后，将新的堆顶元素不断与子节点比较并更新。

新建堆时，不需要逐个插入，可以以O(n)的复杂度新建。首先将所有元素构成一棵完全二叉树。然后从叶子节点开始，将所有节点向下调整。

操作	时间复杂度
插入	$O(logn)$
删除	$O(logn)$
建堆	$O(n)$

代码

和下一篇快速选择算法相同，同样以力扣215题为例。

class Solution {
private:
    void down(vector<int>&a, int i, int heapSize) {
        int l = i * 2 + 1, r = i * 2 + 2, largest = i;
        if (l < heapSize && a[l] > a[largest]) {
            largest = l;
        }
        if (r < heapSize && a[r] > a[largest]) {
            largest = r;
        }
        if (largest != i) {
            swap(a[i], a[largest]);
            down(a, largest, heapSize);
        }
    }

public:
    int findKthLargest(vector<int>& nums, int k) {
        vector<int> heap(nums.size());

        for (int i = 0; i < nums.size(); i++) {
            heap[i] = nums[i];
        }
        for (int i = nums.size() / 2 - 1; i >= 0; i--) {
            down(heap, i, nums.size());
        }

        int heapSize = nums.size();

        for (int i = 0; i < k - 1; i++) {
            swap(heap[0], heap[heapSize - 1]);
            heapSize--;
            down(heap, 0, heapSize);
        }
        
        return heap[0];
    }
};

（事实上这道题可以直接将原数组作为堆处理）