堆的基础知识

小飞侠xp

发布于 2018-08-29 14:40:44

3280

发布于 2018-08-29 14:40:44

二叉堆是非线性的树形的数据结构，有两种堆，最大堆与最小堆。最大堆，树种各个父节点的值总是大于或等于任何一个子节点的值;最小堆，树种各个父节点的值总是小于或等于任何一个子节点的值。我们一般使用二叉堆来实现优先级队列，它的内部调整算法复杂度为log(N)，标准STL的优先级队列包括如下5种操作，设堆H: 1.取出堆顶元素:H.top(); 2.判断堆是否为空:H.empty(); 3.将元素x添加至堆:H.push(x) 4.弹出堆顶:H.pop(); 5.求堆存储元素的个数:H.size()

#include<stdio.h>
#include<queue>
int main(){
    std::priority queue<int> big_heap;//默认构造最大堆
    std::priority queue<int,std::vector<int>,std::greater<int>> small_heap;//最小堆构造方法
    std::priority queue<int,std::vector<int>,std::less<int>> big_heap2;//最大堆构造方法
    if(big_heap.empty()){
        printf("big_heap is empty\n");
    }
    int test[] = {6,10,1,7,99,4,33};
    for(int i = 0;i<7;i++){
        big_heap.push(test[i]);
    }
    printf('"big_heap.top = %d\n",big_heap.top());
    big_heap.push(1000);
    printf("big_heap.top = %d\n",big_heap.top());
    for(int i = 0;i<3;i++){
        big_heap.pop();
    }
    printf("big_heap.top = %d\n",big_heap.top());
    printf("big_heap.size = %d\n",big_heap.size());
}

数组中第K大的数

LeetCode 215. Kth Largest Element in an Array 已知一个未排序的数组，求这个数组中第K大的数字。思考如何使用堆(优先级队列)解决这个问题。如，array = [3,2,1,5,6,4] ， k = 2，return 5

算法设计

维护一个K大小的最小堆，将数组中的元素按顺序push进入堆，push时进行如下操作，堆顶就是第K大的数。堆中存储的元素是前K大的数。堆中元素个数小于K时，新元素直接进入堆;否则，当堆顶小于新元素时，弹出堆顶，将新元素加入堆。

解释：

由于堆是最小堆，堆顶是堆中最小元素，新元素都会保证比堆顶小(否则新元素替换堆顶)，故堆中K个元素是已扫描的元素里最大的K个;堆顶即为第K大的数。

eg array = [3,2,1,5,6,4]，K = 2 :

#include<vector>
#include<queue>
class Solution{
public:
    int findKthLargest(std::vector<int> &nums,int k){//最小堆
    std::priority queue<int, std::vector<int>,std::greater<int>>Q;
    for(int i = 0;i<nums.size();i++){
        if(Q.size()<k){//遍历nums数组
            Q.push(noms[i]);//如果堆中元素个数小于k,直接push进入堆
        }
        else if(Q.top() < nums[i] ){//如果堆顶比新元素小，弹出堆顶，push进新元素（替换堆顶）
            Q.pop();
            Q.push(nums[i]);
            
        }
    }
    return Q.top();
}
}；

测试与leetcode提交

int main(){
    std::vector<int> nums;
    nums.push_back(3);
    nums.push_back(2);
    nums.push_back(1);
    nums.push_back(5);
    nums.push_back(6);
    nums.push_back(4);
    Solution solve;
    printf("%d\n",solve.findKthLargest(nums,2));
    return 0;
}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2018.03.09 ，如有侵权请联系 cloudcommunity@tencent.com 删除

数据结构