<数据结构/算法> 我一定要学会【堆】-第k大

我一定要学会【堆】

气死了，每次写关于堆的算法都要重新复习一遍，今天一定要搞清楚。

什么是堆

堆是一种数据结构，其中的数据以完全二叉树的逻辑组织，但是存储数据的结构使用的是数组。也就是说，要用数组表示一个树的结构。堆分为两种：

• 大根堆：树中任何一个节点大于或等于他的两个孩子节点。
• 小根堆：与大根堆相反。

我们这里以大根堆为例。

堆在数组中存放的顺序是层序，也就是说先存第一层，再存第二层，……由于堆是完全二叉树，所以在数组中存放时，每个节点与其左右孩子节点的位置关系都是可以确定的。

• 父节点位置：k
• 左孩子位置：2k+1
• 右孩子位置：2k+2

堆的调整

由于堆的结构特殊性，所以先要了解堆的调整策略。堆的调整是将不符合堆的结构调整成符合堆的数据结构，分为向上调整和向下调整。

向上调整

向上调整又叫上浮，发生在堆底（也就是末尾）插入新元素的时候，这时要把插入的元素调整到正确的位置，具体做法是确定父节点的位置，与之比较，如果比父节点大就和父节点交换，直到比父节点小，被管住了，就老实呆在那里了。代码如下

void adjustUp(vector<int>& heap, int child){
    int parent = (child - 1) / 2;
    while(parent >= 0 && heap[child] > heap[parent]){
        int tmp = heap[parent];
        heap[parent] = heap[child];
        heap[child] = tmp;
        child = parent;
        parent = (child - 1) / 2;
    }
}

向下调整

向下调整又叫下沉，发生在堆顶元素改变时。此时需要堆顶元素与两个孩子比较，假如父节点元素不是最大的，说明父节点管不住孩子了，需要将其中最大的孩子扶持为新的堆顶，如此循环直到父节点比他的两个孩子都大。

void adjustDown(vector<int>& heap, int parent){
    int lchild = 2 * parent + 1;
    int rchild = lchild + 1;
    while(lchild < heap.size()){
        int largest = lchild;
        
        if(rchild >= heap.size() || heap[lchild] > heap[rchild])
            largest = rchild;
        
        if(heap[parent] > heap[largest])
            break;
        
        int tmp = heap[parent];
        heap[parent] = heap[largest];
        heap[largest] = tmp;
        
        parent = largest;
        lchild = 2 * parent + 1;
        rchild = 2 * parent + 2;
    }
}

插入元素

现在有了两种调整堆的方法，很容易就能插入元素。把元素放到堆底并向上调整就行。

void heapInsert(vector<int>& heap, int val){
    heap.push_back(val);
    adjustUp(heap, heap.size() - 1);
}

堆的创建

那创建堆不就是一个一个元素往堆里面插入吗？

void buildHeap(vector<int>& heap, vector<int>& nums){
    for(int i = 0; i < nums.size(); i++){
        heapInsert(heap, nums[i]);
    }
}

但是这样其实多做了很多无意义的操作，事实上，只要从孩子一步一步往父节点调整就够了，调整次数为logn，即：

void buildHeap(vector<int>& nums){
    for(int i = (nums.size() - 1) / 2; i >= 0; i--){
        adjustDown(nums, i);
    }
}

太神奇了，这甚至是在原数组上就进行了，相当于对于倒数第二层的节点，首先调整以他们为堆顶的子堆，满足大根堆的性质（使用向下调整），然后调整他们父母为顶的子堆，满足大根堆的性质，直到调整到整个堆的顶部，就能保证整个堆满足了大根堆的性质。

删除元素

删除任何一个元素都是一样的，只需要把这个元素放到最后，然后把堆的大小一缩，诶，那个元素就被挡在外面了。那么原本末尾的元素呢，就放到删掉的元素的原本的位置，也就是位置互换了。互换之后末尾的元素还在堆内，但是不满足堆的性质了，所以需要根据和父节点、两个子节点的大小关系判断该选择上浮还是下沉。但是一般我们常用的就是删除堆顶，那堆顶都删没了，新进来的元素肯定没有第二层的大呀，所以需要下沉调整。

这里注意，有的时候我们只是需要形式上把堆顶拿出来，放在后面，并不需要真的把它从这个数组中删掉，只是不在堆中了。这时我们可以使用一个元素来代表堆的末尾指针。

void heapPop(vector<int>& heap, int end){
    int tmp = heap[end];
    heap[end] = heap[0];
    heap[0] = tmp;
    adjustDown(heap, 0);
}

堆的应用-第k大元素

堆在找第k大这种问题上应用比较多。具体就是使用我们的删除操作，每轮删掉一个最大的，这样删k轮就找到第k大了。

int findKth(vector<int>& nums, int k){
    buildHeap(nums);
    int end = nums.size() - 1;
    for(int i = 0; i < k; i++){
        heapPop(nums, end);
        end--;
    }
    return end + 1;
}

但是其实这样是绕了弯路的，因为需要首先建堆，然后一次一次地调整。如果我们换一种思路呢？我们可以用大根堆维护所有的元素，那我们也可以用一个小根堆维护前k大的元素，这个时候小根堆的堆顶就是第k大的元素，每来一个数就和堆顶比较一下，如果比堆顶小，那么说明数组中已经发现了k个比堆顶元素大的数，那么堆顶显然就不可能是前k大的元素之一了，应该被踢掉。如此遍历整个数组，就能得到整个数组前k大的数构成的小根堆，堆顶就是第k大的元素。

int findKth(vector<int>& nums, int k){
	vector<int> heap;
	for(int i = 0; i < k; i++){
		heapInsert(heap, nums[k]);	//注意这里的heapInsert应该根据小根堆来写
	}
	for(int i = k; i < nums.size(); i++){
		if(nums[i] > heap[0]){
			heap[0] = nums[i];	//替换掉堆顶
			adjustDown(heap, 0);	//向下调整
		}
	}
	return heap[0];
}