目录

💡前言一，优先级队列的使用二，仿函数1，什么是仿函数2，仿函数的简单示例

三，优先级队列的底层剖析

💡前言

优先队列(priority_queue)是一种容器适配器，默认使用vector作为其底层存储数据的容器，在vector上又使用了堆算法将vector中元素构造成堆的结构，因此priority_queue就是堆，所有需要用到堆的位置，都可以考虑使用priority_queue。注意：默认情况下priority_queue是大堆。

注意：使用优先级队列要包含头文件 < queue >。

一，优先级队列的使用

代码实现如下：

这里的建堆一般有两种方式：

(1) 一种是一个一个push进vector容器再进行向上调整建堆

(2) 另一种是直接用迭代器区间构造直接建堆(推荐用这种)。

<code>#include <iostream>

#include <queue>

#include <functional>

using namespace std;

void test_priority_queue()

{

vector<int> v = { 6,0,3,5,4,7,9,1,2,8 };

//默认升序

//priority_queue<int> pq(v.begin(), v.end());

//一个一个尾插建堆

priority_queue<int, vector<int>, greater<int>> pq;

for (auto e : v)

{

pq.push(e);

}

//迭代器区间构造，直接建堆

//priority_queue<int,vector<int>,greater<int>> pq(v.begin(), v.end());

while (!pq.empty())

{

cout << pq.top() << " ";

pq.pop();

}

cout << endl;

}

int main()

{

test_priority_queue();

return 0;

}

注意：优先级队列默认的大堆，降序排列，如果要升序，就要换仿函数。下图中第三个模板参数就是传仿函数。

使用算法库里的 less 和 greater 算法，需要包含头文件< functional >

二，仿函数

1，什么是仿函数

仿函数也叫函数对象，是一个重载了 operator() 的类，可以使得类的对象像函数一样使用。

2，仿函数的简单示例

operator()并没有参数的个数和返回值，所以使用是十分灵活的。

<code>struct Func1

{

//无参无返回值

void operator()()

{

cout << "Func调用" << endl;

}

};

struct Func2

{

//有参无返回值

void operator()(int n)

{

while (n--)

{

cout << "Func调用" << endl;

}

}

};

int main()

{

Func1 f1;

f1(); //使得对象像函数一样使用

f1.operator()(); //显示调用

cout << endl;

Func2 f2;

f2(3); //使得对象像函数一样使用

return 0;

}

三，优先级队列的底层剖析

<code>namespace ling

{

template<class T>

class myless

{

public:

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

{

return x < y;

}

};

template<class T>

class mygreater

{

public:

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

{

return x > y;

}

};

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

class priority_queue

{

public:

priority_queue() = default;

//迭代器区间构造

template <class InputIterator>

priority_queue(InputIterator first, InputIterator last)

{

while (first != last)

{

con.push_back(*first);

++first;

}

//建堆

for (int i = (con.size() - 1 - 1) / 2; i >= 0; i--)

{

Adjust_down(i);

}

}

bool empty() const

{

return con.empty();

}

size_t size() const

{

return con.size();

}

// 堆顶元素不允许修改，因为：堆顶元素修改可以会破坏堆的特性

const T& top()const

{

return con[0];

}

//向上调整

void Adjust_up(int child)

{

int parent = (child - 1) / 2;

while (child > 0)

{

//if (con[parent] < con[child])

if(comp(con[parent], con[child]))

{

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

child = parent;

parent = (child - 1) / 2;

}

else

{

break;

}

}

}

void push(const T& x)

{

con.push_back(x);

Adjust_up(con.size() - 1);

}

//向下调整

void Adjust_down(int parent)

{

int child = parent * 2 + 1;

while (child < con.size())

{

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

{

child += 1;

}

//if (con[parent] < con[child])

if(comp(con[parent], con[child]))

{

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

parent = child;

child = parent * 2 + 1;

}

else

{

break;

}

}

}

void pop()

{

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

con.pop_back();

Adjust_down(0);

}

private:

Container con;

Compare comp;

};

}

测试代码：

void TestQueuePriority()

{

ling::priority_queue<int> q1;

q1.push(5);

q1.push(1);

q1.push(4);

q1.push(2);

q1.push(3);

q1.push(6);

cout << q1.top() << endl;

q1.pop();

q1.pop();

cout << q1.top() << endl;

vector<int> v{ 5,1,4,2,3,6 };

ling::priority_queue<int, vector<int>, ling::greater<int>> q2(v.begin(), v.end());

cout << q2.top() << endl;

q2.pop();

q2.pop();

cout << q2.top() << endl;

}