一. 优先级队列简介

        首先，它的本质就是一个堆（heap）。

在C++中，优先级队列（Priority Queue）是一种特殊的容器适配器，它提供了一个能实现类似堆的结构的功能。优先级队列保证了队首元素总是最大的（或者在最小的元素在优先级最高的定义下是最小的），与普通队列不同，优先级队列的出队操作（front和pop）总是取出具有最高优先级的元素，而入队操作（push）会将新元素插入到正确的位置以保持优先级顺序。这种顺序是通过堆这种数据结构来实现的。

在实践中，优先级队列通常用于需要快速检索最大（或最小）元素的场景，例如在图算法中的Dijkstra算法，或者在处理事件时根据事件的优先级来排序。

二. 使用示例

在C++标准库中，优先级队列（std::priority_queue）是在<queue>头文件中定义的。它有以下几个基本操作：

<code>empty()：判断优先级队列是否为空。size()：返回优先级队列中元素的数量。top()：返回队首元素，即优先级最高的元素。push(const T& value)：向优先级队列中添加一个元素,并自动根据优先级排序。pop()：移除并返回队首元素（优先级最高的元素）。

在使用它时要注意，它默认使用 std::less 作为比较函数，这意味着它默认构建的是最大堆。如果你想创建一个最小堆，你可以在创建优先级队列时提供一个不同的比较函数，比如 std::greater 。

下面是一个简单的例子，展示了如何在C++中使用优先级队列：

#include <iostream>

#include <queue>

int main() {

std::priority_queue<int> pq; // 默认创建最大堆

pq.push(1);

pq.push(2);

pq.push(3);

pq.push(4);

pq.push(5);

while (!pq.empty()) {

std::cout << pq.top() << " "; // 输出:5 4 3 2 1

pq.pop();

}

return 0;

}

创建它时，还可以指定底层元素类型，容器类型（默认为std::vector）以及可选的比较对象。

比如下面的最小堆：

#include <iostream>

#include <queue>

int main() {

std::priority_queue<int, std::vector<int>, std::greater<int>> pq; // 创建最小堆

pq.push(5);

pq.push(4);

pq.push(3);

pq.push(2);

pq.push(1);

while (!pq.empty()) {

std::cout << pq.top() << " "; // 输出:1 2 3 4 5

pq.pop();

}

return 0;

}

这样就改变了队列的优先级。

三. 模拟实现 priority_queue

因为优先级队列的底层和 堆 的实现逻辑相同，所以得先实现向上调整算法，和向下调整算法，这里因为要适配优先级队列，所以会稍微有点差别。这里建的是一个大顶堆。

1.堆的写法应该是这样：

// 大顶堆

// 向上调整

void adjust_up(size_t child) {

size_t parent = (child - 1) / 2;

while (child > 0) {

if (arr[parent] > arr[child]) {

swap(c[parent], c[child]);

child = parent;

parent = (parent - 1) / 2;

}

else

break;

}

}

// 向下调整

void adjust_down(size_t parent) {

size_t child = parent * 2 + 1;

while (child < c.size()) {

if (child + 1 < c.size() && arr[child] > arr[child+1])

child++;

if (arr[parent] > arr[child]) {

swap(c[parent], c[child]);

parent = child;

child = child * 2 + 1;

}

else

break;

}

}

而在优先级队列中是这样写的：

template<class T>

struct Greater

{

bool operator()(const T& x, const T& y) {

return x > y;

}

};

template<class T>

struct Less

{

bool operator()(const T& x, const T& y) {

return x < y;

}

};

template <class T, class Container = vector<T>, class Compare = less<T> >

class priority_queue

{

public:

void adjust_up(size_t child) {

size_t parent = (child - 1) / 2;

while (child > 0) {

if (comp(c[parent], c[child])) {

swap(c[parent], c[child]);

child = parent;

parent = (parent - 1) / 2;

}

else

break;

}

}

void adjust_down(size_t parent) {

size_t child = parent * 2 + 1;

while (child < c.size()) {

if (child + 1 < c.size() && comp(c[child], c[child + 1]))

child++;

if (comp(c[parent], c[child])) {

swap(c[parent], c[child]);

parent = child;

child = child * 2 + 1;

}

else

break;

}

}

// ......

private:

Container c;

Compare comp;

};

可以看到这里因为有两个优先级，所以用到了两个重载了 ( ) 操作符的仿函数，使其可以像函数一样被调用，这一点很像C语言中的函数调用。

完整实现代码

#include<vector>

using namespace std;

namespace pq

{

template<class T>

struct Greater

{

bool operator()(const T& x, const T& y) {

return x > y;

}

};

template<class T>

struct Less

{

bool operator()(const T& x, const T& y) {

return x < y;

}

};

// 默认建大顶堆

template <class T, class Container = vector<T>, class Compare = less<T> >

class priority_queue

{

public:

priority_queue(){}

void adjust_up(size_t child) {

size_t parent = (child - 1) / 2;

while (child > 0) {

if (comp(c[parent], c[child])) {

swap(c[parent], c[child]);

child = parent;

parent = (parent - 1) / 2;

}

else

break;

}

}

void adjust_down(size_t parent) {

size_t child = parent * 2 + 1;

while (child < c.size()) {

if (child + 1 < c.size() && comp(c[child], c[child + 1]))

child++;

if (comp(c[parent], c[child])) {

swap(c[parent], c[child]);

parent = child;

child = child * 2 + 1;

}

else

break;

}

}

bool empty() const {

return c.empty();

}

size_t size() const {

return c.size();

}

T& top() const {

if (empty())

return;

return c[0];

}

void push(const T& x) {

c.push_back(x);

adjust_up(c.size() - 1);

}

void pop() {

if (empty())

return;

swap(c[0], c[c.size() - 1]);

c.pop_back();

adjust_down(0);

}

private:

Container c;

Compare comp;

};

}