C++ priority_queue用法介绍

1.描述

priority_queue是优先队列，相对于普通的队列来说，它可以定义数据的优先级，在队列里面元素被赋予优先级，优先级高的优先出队列。优先队列具有队列的所有特性，包括基本操作，只是在这基础上添加了内部的一个排序，它本质是一个堆实现的。默认是大堆，即大的元素优先出队列。

2.定义

在使用时需要引入头文件 #include <queue>，常见的有两种声明方式，如下：

std::priority_queue<T> pq;
std::priority_queue<T, std::vector<T>, cmp> pq;

STL中声明如下：

template <class Type, class Container= vector <Type>, class Compare= less <typename Container ::value_type>>
class priority_queue

其中：

Type 数据类型

Container 存放数据容器类型，默认是vector，也可以是dequeue。

Compare 比较器

3.示例

void test_priority1()
{
    priority_queue<int> queue;
    queue.push(4);
    queue.push(2);
    queue.push(8);
    queue.push(10);
    queue.push(25);
    int  size = queue.size();
    for(int i=0;i < size; i++){
        cout<<queue.top()<<endl;
        queue.pop();
    }
}

运行结果：

25
10
8
4
2

调整为小根堆，默认输出小元素。

void test_priority2()
{
    priority_queue<int, vector<int>, greater<int> > queue;
    queue.push(4);
    queue.push(2);
    queue.push(8);
    queue.push(10);
    queue.push(25);
    int  size = queue.size();
    for(int i=0;i < size; i++){
        cout<<queue.top()<<endl;
        queue.pop();
    }
}

输出结果：

2
4
8
10
25