深入理解C++优先级队列：原理解析与代码实战

C嘎嘎探索篇：优先级队列：在数据之舞中揭开算法的艺术面纱

前言：

小编在前几日刚刚完成了栈和队列相关内容的书写，今天小编在讲一种特殊的队列，它的名字叫做优先级队列，细心的读者朋友可能会发现在queue这个头文件中，不仅仅只有queue适配器，还有一个priority_queue适配器，这就是优先级队列，虽然说它的名字中队列这里两个字，但其实它就是我们曾经学习过的堆结构，下面我们小编就进入优先级队列的讲解环节。 正文：

1.priority_queue的介绍和使用

1.1.priority_queue的介绍

优先级队列是一种容器适配器，根据严格的弱排序标准，它的第一个元素在它包含的元素中最大的，它就是我们之前在数据结构阶段实现的大堆结构，当时我们堆是用顺序表进行时间的（顺序二叉树），所以此时我们的优先级队列同样可以用vector进行封装，所以它此时不再是一个容器，而是一个容器的适配器，在等会的模拟实现中相信各位可以更好的知晓这个特点，可能有很多读者朋友并没有学过堆这个数据结构，那么可以看看小编之前写过的堆结构的文章：数据结构——原来二叉树可以这么学？（2：堆的详解）-CSDN博客，在这篇文章中我就详细介绍了堆的相关概念和如何去实现的，我推荐各位看一看这个文章，避免等会听的懵逼，因为我是默认大家是会堆这个结构的，下面废话不多说，小编介绍一下优先级队列相关的功能。

1.2.priority_queue的使用

通过上图可以看出，优先级队列的功能和之前小编讲过的栈和队列一样都很少，因为堆这个结构也是很特殊的，它是一个二叉树样子的结构，每次我们插入元素的时候都需要用到调整建堆的方法来维持大堆或者小堆，堆是小编认为数据结构中比较麻烦的结构之一，下面我就开始讲述一下相关接口，和之前一样，功能小编一般就讲述一部分的功能，如果全讲出来也是没有什么必要的，因为有些功能说实在的是有一些鸡肋的，所以我就挑重点的进行讲述，感兴趣的读者朋友可以自行探索别的功能。

1.2.1.priority_queue()

这个接口的写法在大多数容器和适配器都能体现出来，它其实就是我们熟悉的构造函数，只不过这个是不带参的构造函数，所以我们用它的时候，会建造一个空的优先级队列，用堆的话来讲，就是制造一个空的堆，下面小编展示和这个接口的用法：

using namespace std;
priority_queue<int> s1;  //这样就可以构造一个空的优先级队列

1.2.2.empty()

这个接口的功能也是很好去记忆的，它的功能和它的名字是相互对应着的，所以它的功能就是判断优先级队列是否为空，如果为空的话就返回真，如果满的滑稽就返回假，下面小编展示它的用法：

using namespace std;
priority_queue<int> s1;
if(s1.empty())
{
    cout << 1 << endl;
}
cout << 2 << endl; //很明显此时我并没有进行入堆的操作，所以此时为空，打印的是1，这里我就不展示结果了

1.2.3.push(x)

这个函数的作用同样也是十分的容易，它一眼看去就是一个插入元素的函数，只不过这个函数其实底层并不只是简单的进行插入元素的操作，小编说过，优先级队列就是我们之前学习过的堆结构，堆结构我们在插入元素（入堆）的时候就涉及到了元素的调整问题，此时的插入接口也会进行这样的操作，这和队列的优先级有关，它的优先级的控制是由仿函数决定的，对于仿函数的介绍，小编会在下一篇对于优先级队列的模拟实现中好好给各位进行讲述的（本来想一篇文章写完的，但是一篇分为两篇也不是不行，(#.#)），下面小编展示它的用法：

using namespace std;
priority_queue<int> s1;
s1.push(5);
s1.push(3);
s1.push(4);
s1.push(1);  //因为此时的优先级队列默认是大堆，也就是最大元素在最上面，所以此时里面应该是5 3 4 1

1.2.4.pop()

有入堆操作，肯定就有出堆操作，pop这个函数各位也是不陌生了，只不过此时的删除也不是单纯的删除，小编在讲堆的时候，说过出堆操作其实是把第一个元素删除，只不过需要先把堆第一个数据和最后一个数据交换，然后尾删，这样做的话不会破坏中间的二叉树结构，我们仅需在进行一次简单的调整就好了，下面小编展示它的用法：

using namespace std;
priority_queue<int> s1;
s1.push(5);
s1.push(3);
s1.push(4);
s1.push(1);  //因为此时的优先级队列默认是大堆，也就是最12大元素在最上面，所以此时里面应该是5 3 4 1
s1.pop(); //此时把5进行了删除，此时队列里面是：4 3 1

1.2.5.size()

这个函数的作用也很简单，它就是返回优先级队列有效元素的个数，所以我就直接展示它的用法了：

using namespace std;
priority_queue<int> s1;
cout << s1.size() << endl; //此时没有插入元素，所以大小应该是0

1.2.6.top()

这个函数的作用也是很好去理解的，它的作用和它的名字一样，就是取堆顶的元素，此时我们通过这个函数，再搭配其他的函数，就可以实现出遍历一个优先级队列的操作，下面小编展示它的用法：

using namespace std;
priority_queue<int> s1;
s1.push(1);
s1.push(2);
s1.push(3);
s1.push(4);
while(!s1.empty())
{
    cout << s1.top() << " ";
    s1.pop();
}
cout << endl;

以上便就是小编对于优先级队列的讲解，这些功能最好去记一下，毕竟堆也是我们之前学过的一个比较重要的数据结构，只不过我还是认为，它的难度还是不大使用起来，只不过在模拟实现的时候会稍微有一点困难，只不过本文我就不写它的模拟实现了，我准备在下一篇文章着重写对于它的模拟实现，各位读者朋友敬请期待吧~

2.总结

本文到这也就结束了，虽然文章的篇幅总体不算很大的，但我认为内容还是蛮丰富的，小编在这篇文章着重的讲述了优先级队列相关的功能，希望各位读者朋友要好好的去理解，最近感觉时间都不够用了，这篇文章我也是鸽了好久才写完，希望以后我可以好好的去分配自己的时间，有点贪玩了，如果文章有任何错误，可以在评论区指出，我会及时的去更改错误，那么各位大佬们，我们下一篇文章见啦~

能，希望各位读者朋友要好好的去理解，最近感觉时间都不够用了，这篇文章我也是鸽了好久才写完，希望以后我可以好好的去分配自己的时间，有点贪玩了，如果文章有任何错误，可以在评论区指出，我会及时的去更改错误，那么各位大佬们，我们下一篇文章见啦