C++优先队列(priority_queue)

78 阅读 0 评论 52 点赞

我是靠谱客的博主大意超短裙，最近开发中收集的这篇文章主要介绍C++优先队列(priority_queue)，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

一、定义

包含头文件#include <queue>

语法：

priority_queue<Type, Container, Functional>

解释：Type为数据类型， Container为保存数据的容器，Functional为元素比较方式。如果不写后两个参数，那么容器默认用的是vector，比较方式默认用operator<，也就是优先队列是大顶堆，队头元素最大。

priority_queue 模拟的是队列这种存储结构，元素只能“从一端进（称为队尾），从另一端出（称为队头）”，且每次只能访问 priority_queue 中位于队头的元素。
但是，priority_queue 中的元素的存和取，遵循的并不是先入先出原则，而是“First in，Largest out”原则。直白的翻译，指的是优先级最大的元素最先出队列。至于优先级，可以自定义，默认是最大的值先出。

二、源码

我们直接查看优先对列的源码，发现它之所以实现了优先级最大的先出，是因为使用了二叉堆这种数据结构，对应的操作有：make_heap，push_heap，pop_heap。

template <class T, 
    class Sequence = vector<T>,
    class Compare = less<typename Sequence::value_type> >
 
class priority_queue {
public:
    typedef typename Sequence::value_type value_type;
    typedef typename Sequence::size_type size_type;
    typedef typename Sequence::reference reference;
    typedef typename Sequence::const_reference const_reference;
 
protected:
    Sequence c; // 底层容器
    Compare comp; // 元素大小比较标准
 
public:
    priority_queue() : c() {}
    explicit priority_queue(const Compare& x) : c(), comp(x) {}
 
    // 以下用到的 make_heap(), push_heap(), pop_heap()都是泛型算法
    // 注意，任一个建构式都立刻于底层容器内产生一个 隐式的heap
    template <class InputIterator>
    priority_queue(InputIterator first, InputIterator last, const Compare& x)
        : c(first, last), comp(x) { make_heap(c.begin(), c.end(),comp); }

    template <class InputIterator>
    priority_queue(InputIterator first, InputIterator last)
        : c(first, last) { make_heap(c.begin(), c.end(), comp); }
 
    bool empty() const { return c.empty(); }

    size_type size() const { return c.size(); }

    const_reference top() const { return c.front(); }

    void push(const value_type& x) {
        __STL_TRY {
            // push_heap是泛型算法，先利用底层容器的 push_back() 将新元素推入末端，再重排heap
            c.push_back(x);
            push_heap(c.begin(), c.end(), comp); //push_heap是泛型算法
        }
        __STL_UNWIND(c.clear());
    }
    void pop() {
        __STL_TRY {
            //pop_heap 是泛型算法，从 heap 内取出一个元素。它并不是真正将元素
            //弹出，而是重排 heap，然后再以底层容器的 pop_back() 取得被弹出的元素
            pop_heap(c.begin(), c.end(), comp);
            c.pop_back();
        }
        __STL_UNWIND(c.clear());
    }
};

同时可以看到，priority_queue 容器适配器模板类最多可以传入 3 个参数，它们各自的含义如下：

typename T：指定存储元素的具体类型；
typename Container：指定 priority_queue 底层使用的基础容器，默认使用 vector 容器。

作为 priority_queue 容器适配器的底层容器，其必须包含 empty()、size()、front()、push_back()、pop_back() 这几个成员函数，STL 序列式容器中只有 vector 和 deque 容器符合条件。priority_.queue不提供遍历功能，也不提供迭代器。

三、使用

3.1 直接使用系统提供的仿函数

//升序队列
priority_queue <int,vector<int>,greater<int>> q;

//降序队列
priority_queue <int,vector<int>,less<int>>q;

//greater和less是std实现的两个仿函数，这里less是从大到小排列，greater是小到大排列

实例

#include<iostream>
#include <queue>
using namespace std;
int main() 
{
    // 对于基础类型 默认是大顶堆
    priority_queue<int> a;
    // 等同于 priority_queue<int, vector<int>, less<int>> a;

    priority_queue<int, vector<int>, greater<int>> c;  //这样就是小顶堆

    priority_queue<string> b;

    for (int i = 0; i < 5; i++)
    {
        a.push(i);
        c.push(i);
    }

    while (!a.empty())
    {
        cout << a.top() << ' ';
        a.pop();
    }
    cout << endl;

    while (!c.empty())
    {
        cout << c.top() << ' ';
        c.pop();
    }
    cout << endl;

    b.push("abc");
    b.push("abcd");
    b.push("cbd");

    while (!b.empty())
    {
        cout << b.top() << ' ';
        b.pop();
    }
    cout << endl;

    system("pause");
    return 0;
}

3.2 自定义仿函数

#include<cstdio>
#include<queue>
using namespace std;

struct node
{
	int x,y;
	bool operator < (const node & a) const
	{
		return x<a.x;
	}
}k;
priority_queue <node> q;

int main()
{
	k.x=10,k.y=100; q.push(k);
	k.x=12,k.y=60; q.push(k);
	k.x=14,k.y=40; q.push(k);
	k.x=6,k.y=80; q.push(k);
	k.x=8,k.y=20; q.push(k);
	while(!q.empty())
	{
		node m=q.top(); q.pop();
		printf("(%d,%d) ",m.x,m.y);
	}
    system("pause");
    return 0;
}