admin管理员组

文章数量:1623784

c++中的堆-priority_queue的使用方法

    • 1 priority_queue的底层实现
    • 2 priority_queue基本操作
      • 2.1 已有数据类型初始化
      • 2.2 自定义数据结构的堆
      • 2.3 基本操作(和queue相似操作)
    • 3 堆的使用场景

堆作为一个重要的数据结构，应该是接触编程的人员都会了解的，本文是在写leetcode中，由于需要经常使用到堆这一数据结构而写的学习记录帖。即使手撸一个堆并不复杂，但是还是大大拖慢的写题节奏，更何况自己写的堆无论是效率还是安全性咱也没什么信息，这就是STL各个模板发挥的时候了。这里就来简单介绍一下priority_queue，即优先队列。

1 priority_queue的底层实现

PriorityQueue中的元素在逻辑上构成了一棵完全二叉树，但实际这个堆结构在物理存储上是用数组实现的。如果有兴趣了解，可以看看这个博客。

2 priority_queue基本操作

2.1 已有数据类型初始化

小根堆初始化
priority_queue<int,vector<int>,greater<int>> p
大根对初始化
priority_queue<int,vector<int>,less<int>> p
三个参数的意思：

/*
@para p1 :该队列盛放的数据类型
@para p2 :container，需要是数组实现，一般就是vector
@para p3 :比较器，（因为涉及到了比较排序嘛
*/

一般如果我们要使用大根堆且不用自定义的数据结构，只要填写第一个参数即可:
priority_queue<int> p
对于一些已由的数据类型，我们就免去了定义比较器的麻烦，直接使用greater<>或less<>即可。值得注意的是，对于tuple和pair这样的结构，也已经定义好了比较器:

  1. pair举例
//默认是使用大根堆
priority_queue<pair<int,int>> pq0;
//小根堆，按照pair的first排，再按照second排序
priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> pq1;
//大根堆
priority_queue<pair<

本文标签： 使用方法priorityqueue

版权声明：本文标题：c++中的堆-priority_queue的使用方法 内容由热心网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：https://www.elefans.com/dianzi/1728896267a1178449.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。