一：优先队列priority_queue简介

同队列，不支持迭代

（一）和队列相比

同：

优先队列容器与队列一样，只能从队尾插入元素，从队首删除元素。

异：

但是它有一个特性，就是队列中最大的元素总是位于队首，所以出队时，并非按照先进先出的原则进行，而是将当前队列中最大的元素出队。这点类似于给队列里的元素进行了由大到小的顺序排序。

补充：元素之间比较

元素的比较规则默认按元素值由大到小排序，可以重载“<”操作符来重新定义比较规则。

（二）重点：同vector，deque，list，以及queue比较

虽然与queue相似，但是之所以不放在queue之后讲，是因为实现优先队列是要依靠容器的迭代器实现的，而queue和stack是没有迭代功能的。而且stl中优先队列是基于vector和deque实现的，是基于这两种容器的迭代特性实现--->支持随机存取迭代这也是为什么优先队列不可以基于list实现--->list不支持随机存取迭代

二：优先队列priority_queue的构造

priority_queue<int, vector<int>, cmp> q; //定义方法 //其中第一个是数据类型，第二个参数为容器类型：默认是vector。第三个参数为比较函数：默认less。

案例1：默认最大值优先

priority_queue<int, deque<int>> pq;　　//基于双端队列 priority_queue<int, vector<int>> pq;　 //基于向量 上面是默认最大值优先

案例2：修改比较方式

priority_queue<int,vector<int>, less<int>> pq1; 　　　 // 使用递减 less<int>函数对象排序 首位最大 priority_queue<int,deque<int>, greater<int>> pq2; 　　 // 使用递增greater<int>函数对象排序 首位最小

三：优先队列常用操作

q.empty() 如果队列为空，则返回true，否则返回false q.size() 返回队列中元素的个数 q.pop() 删除队首元素，但不返回其值 q.top() 返回具有最高优先级的元素值，但不删除该元素 q.push(item) 在基于优先级的适当位置插入新元素 priority_queue<int,vector<int>> pq; pq.push(5); pq.push(50); pq.push(16); while (!pq.empty()) { cout << pq.top() << " "; pq.pop(); }

四：自定义比较结构

struct cmp1{ bool operator ()(int &a,int &b){ return a>b;//最小值优先 } }; void main() { priority_queue<int,vector<int>,cmp1> pq; pq.push(5); pq.push(50); pq.push(16); while (!pq.empty()) { cout << pq.top() << " "; pq.pop(); } system("pause"); }

五：自定义数据结构（重载<比较运算符）

struct number1{ int x; bool operator < (const number1 &a) const { return x>a.x;//最小值优先 } }; void main() { priority_queue<number1, vector<number1>> pq; number1 n1, n2, n3; n1.x = 5; n2.x = 50; n3.x = 16; pq.push(n1); pq.push(n2); pq.push(n3); while (!pq.empty()) { cout << pq.top().x << " "; pq.pop(); } system("pause"); }

数据结构（四）树---哈夫曼树了解以及代码实现

转载于:https://www.cnblogs.com/ssyfj/p/10789732.html

相关资源：各显卡算力对照表！