优先队列（堆）的实现

发表于 更新于 分类于 阅读次数：
本文字数： 1.3k 阅读时长 ≈ 1 分钟

优先队列（堆）

优先队列也就是堆

什么是堆呢？

堆是一颗完全二叉树，树中每个结点的值都不小于（或不大于）其左右孩子的值。 如果父亲结点是大于等于左右孩子就是大顶堆，小于等于左右孩子就是小顶堆。

priority_queue<int , vector<int>,greater<int>> heap;//创建小根堆

1
2
3
4
5
6
7
8
9
10
11

引用头文件 #include<queue>
top 访问队头元素
empty 队列是否为空
size 返回队列内元素个数
push 插入元素到队尾 (并排序)
emplace 原地构造一个元素并插入队列
pop 弹出队头元素
swap 交换内容


1
2
3
4
5
6
7
8
9
10
11
12
13
14
std::priority_queue<T> pq;
std::priority_queue<T, std::vector<T>, cmp> pq;

//自定义比较类型
//左大于右就会建立小顶堆，反而建立大顶堆

// 小顶堆--pair类型的比较
class mycomparison {
public:
    bool operator()(const pair<int, int>& lhs, const pair<int, int>& rhs) {
        return lhs.second > rhs.second;
    }
};

练习题目

Leetcode-前K个高频元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {
public:
    // 小顶堆
    class mycmp{
        public:
        bool operator() (const pair<int,int> &l,const pair<int,int> &r)
        {
            return l.second>r.second;
        }
    };
     vector<int> topKFrequent(vector<int>& nums, int k) {
        unordered_map<int,int> map;
        priority_queue<pair<int,int>,vector<pair<int,int>>,mycmp> heap;
        for(int i=0;i<nums.size();++i)
        {
            ++map[nums[i]];
        } 
        for(auto i : map){
            heap.push(i);
            if(heap.size()>k)
            {
                heap.pop();
            }
        }
        vector<int> ans;
        
        while(!heap.empty())
        {
            ans.push_back(heap.top().first);
            heap.pop();
        }
        return ans;
    }
};