前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >堆的基础知识

堆的基础知识

作者头像
小飞侠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()

代码语言:javascript
复制
#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 :
代码语言:javascript
复制
#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提交
代码语言:javascript
复制
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 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 数组中第K大的数
    • 算法设计
      • 解释:
        • eg array = [3,2,1,5,6,4],K = 2 :
          • 测试与leetcode提交
          相关产品与服务
          对象存储
          对象存储(Cloud Object Storage,COS)是由腾讯云推出的无目录层次结构、无数据格式限制,可容纳海量数据且支持 HTTP/HTTPS 协议访问的分布式存储服务。腾讯云 COS 的存储桶空间无容量上限,无需分区管理,适用于 CDN 数据分发、数据万象处理或大数据计算与分析的数据湖等多种场景。
          领券
          问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档