文章目录

📝priority_queue的介绍和使用🌠 priority_queue的介绍🌉priority_queue的使用

🌠仿函数的使用🌠C语言有趣的模仿push_back🌠priority_queue的模拟实现🚩总结

📝priority_queue的介绍和使用

🌠 priority_queue的介绍

<code>priority_queue官方文档:https://legacy.cplusplus.com/reference/queue/priority_queue/?kw=priority_queue

优先队列是一种容器适配器，根据严格的弱排序标准，它的第一个元素总是它所包含的元素中最大的。此上下文类似于堆，在堆中可以随时插入元素，并且只能检索最大堆元素（优先队列中，位于顶部的元素）优先队列被实现为容器适配器，容器适配器即将特定容器类封装作为其底层容器类，queue提供一组特定的成员函数来访问其元素，元素从特定容器的尾部弹出，其称为优先队列的顶部。底层容器可以是任意标准容器类模版，也可以是其他特定设计的容器类。容器应该可以随机访问迭代器访问，并支持以下的操作：

empty()：检测容器是否为空size()：返回容器中有效元素个数front()：返回容器中第一个元素的引用push_back()：在容器尾部插入元素pop_back()：删除容器尾部元素

标准容器类vector和deque满足这些需求。默认情况下，如果没没有为特定的priority_queue类实例化指定容器类，则使用vector.需要支持随机访问迭代器 ，以便始终在内部保持堆结构，容器适配器通过在需要时自动调用算法函数make_heap,push_heap,和pop_heap来完成自动操作

🌉priority_queue的使用

优先级队列默认使用vector作为其底层容器存储数据的容器，在vector上又使用堆算法讲vector中元素构造成堆的结构，因此priority_queue就是堆，所有需要用到堆的成员位置，都可以考虑使用priority_queue。

注意：默认情况下priority_queue是大堆

需要注意的是：

默认情况下，<code>priority_queue是大堆

如果需要要得到小堆，修改比较方式就好，比较方式可以有仿函数，函数指针，函数模板，类模版等等，

比如使用<code>function文件的

正常来说，greate是用来降序，大根堆，这里跟往常使用不同，因此，需要注意！！

如果在<code>priority_queue中放自定义类型的数据，用户需要在自定义类型中提供> 或者< 的重载。

#include "Priority_queue.h"

class Date

{ -- -->

public:

friend ostream& operator<<(ostream& _cout, const Date& d);

Date(int year = 1900, int month = 1, int day = 1)

:_year(year)

,_month(month)

,_day(day)

{ }

bool operator <(const Date& d) const

{

return (_year < d._year)

|| (_year == d._year && _month < d._month)

|| (_year == d._year && _month == d._month && _day < d._day);

}

bool operator >(const Date& d) const

{

return (_year > d._year)

|| (_year == d._year && _month > d._month)

|| (_year == d._year && _month == d._month && _day > d._day);

}

bool operator==(const Date& d)

{

return (_year == d._year

&& _month == d._month

&& _day == d._day);

}

bool operator!=(const Date& d)

{

return (_year != d._year)

|| (_year == d._year && _month != d._month)

|| (_year == d._year && _month == d._month && _day != d._day);

}

private:

int _year;

int _month;

int _day;

};

ostream& operator<<(ostream& _cout, const Date& d)

{

_cout << d._year << "-" << d._month << "-" << d._day;

return _cout;

}

struct PDateless //struct默认为public,comfunc()才能调用，class默认为private

{

bool operator()(Date* p1, Date* p2)

{

return *p1 < *p2;

}

};

void TestPriorityQueue()

{

//大堆，需要用户在自定义类型中提供<重载

own::priority_queue<Date*, vector<Date*>, PDateless> q1;

q1.push(new Date(2024, 9, 13));

q1.push(new Date(2024, 9, 14));

q1.push(new Date(2024, 9, 15));

while (!q1.empty())

{

cout << *q1.top() << " ";

q1.pop();

}

cout << endl;

}

int main()

{

TestPriorityQueue();

return 0;

}

如 在OJ中的使用

数组中的第K个最大元素：https://leetcode.cn/problems/kth-largest-element-in-an-array/description/

class Solution { -- -->

public:

int findKthLargest(vector<int>& nums, int k) {

// 将数组中的元素先放入优先级队列中

priority_queue<int> p(nums.begin(), nums.end());

// 将优先级队列中前k-1个元素删除掉

for (int i = 0; i < k - 1; ++i)

{

p.pop();

}

return p.top();

}

};

🌠仿函数的使用

仿函数/函数对象:重载了operator()的类，类的对象可以像函数一样使用operator()特点，参数个数和返回值根据需求确定，不固定，很灵活

// 定义一个仿函数类

class Add {

public:

// 重载 operator()，接受两个参数并返回它们的和

int operator()(int a, int b) {

return a + b;

}

};

int main() {

// 创建仿函数对象

Add add;

// 使用仿函数

int result = add(3, 4); // 调用 operator()

std::cout << "3 + 4 = " << result << std::endl;

return 0;

}

灵活使用：

class Func

{

public:

void operator()(int n)

{

while (n--)

{

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

}

cout << endl;

}

};

int main()

{

//仿函数

Func f1;

f1(10);

f1.operator()(10);

return 0;

}

🌠C语言有趣的模仿push_back

<code>void PushBack(int x)

{ -- -->

printf("void PushBack(int x)\n");

}

// C

struct Vector

{

void(*push_back)(int);

int* _a;

int _size;

int _capacity;

};

void Init(struct Vector* pv)

{

pv->push_back = PushBack;

//...

}

int main()

{

Vector v;

Init(&v);

v.push_back(1);

v.push_back(2);

return 0;

}

🌠priority_queue的模拟实现

通过对<code>priority_queue的底层结构就是堆，因此此处只需对对进行通用的封装即可。

基本框架

#pragma once

#include <iostream>

#include <vector>

#include <algorithm>

using namespace std;

namespace own

{ -- -->

template<class T>

struct myless

{

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

{

return x < y;

}

};

template<class T>

struct mygreater

{

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;

T& top()

{

return _con[0];

}

size_t size()

{

return _con.size();

}

bool empty()

{

return _con.empty();

}

private:

Container _con;

};

}

使用迭代器添加元素数据进数组：

当数据都进vector容器，我们随带建堆：

template<class InputIterator>

priority_queue(InputIterator first, InputIterator last)

{

while (first != last)

{

_con.push_back(*first);

++first;

}

//从顶开始建堆

for (size_t i = 0 ;i < _con.size();++i)

{

adjustup(i);

}

}

建堆两种方式：向上建堆：向下建堆：

<code>//第一种

void adjustup(size_t child)

{ -- -->

Compare comfunc;

while (child > 0)

{

size_t parent = (child - 1) / 2;

if (comfunc(_con[parent], _con[child]))

{

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

child = parent;

parent = child * 2 + 1;

}

else

{

break;

}

}

}

//第二种

void adjustup(int child)

{

Compare comfunc;

while (child > 0)

{

size_t parent = (child - 1) / 2;

if (comfunc(_con[parent], _con[child]))

{

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

child = parent;

//加不加这个parent都可以，因为上面可以再次获取,加了可以方便理解

//parent = (child - 1) / 2;

}

else

{

break;

}

}

//}

//第三种

//也可以是这样的写法

void adjustup(int child)

{

Compare comfunc;

size_t parent = (child - 1) / 2;

//

// 注意：这里的parent 和child的顺序要和adjustdown的if (comfunc(_con[parent] , _con[child]))比较顺序一致

while (comfunc(_con[parent] , _con[child])) {

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

child = parent;

parent = (child - 1) / 2;

}

}

向下调整建堆：

void adjustdown(int parent)

{

Compare comfunc;

size_t child = 2 * parent + 1;

while (child < _con.size())

{

if (child + 1 < _con.size() && comfunc(_con[child] , _con[child + 1]))

{

++child;

}

if (comfunc(_con[parent] , _con[child]))//注意：这里的parent 和child的顺序要和adjustupwhile (comfunc(_con[parent] , _con[child]))顺序一致

{

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

parent = child;

child = 2 * parent + 1;

}

else

{

break;

}

}

}

两个操作push和pop

<code>void push(const T& x)

{ -- -->

_con.push_back(x);

adjustup(_con.size() - 1);

}

void pop()

{

std::swap(_con[0], _con[_con.size()-1]);

_con.pop_back();

adjustdown(0);

}

priority_queue的源代码：

<code>#pragma once

#include <iostream>

#include <vector>

#include <algorithm>

using namespace std;

namespace own

{ -- -->

template<class T>

struct myless

{

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

{

return x < y;

}

};

template<class T>

struct mygreater

{

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 (size_t i = 0 ;i < _con.size();++i)

{

adjustup(i);

}

}

//void adjustup(size_t child)

//{

//Compare comfunc;

//while (child > 0)

//{

//size_t parent = (child - 1) / 2;

//if (comfunc(_con[parent], _con[child]))

//{

//swap(_con[parent], _con[child]);

//child = parent;

//parent = child * 2 + 1;

//}

//else

//{

//break;

//}

//}

//}

//void adjustup(int child)

//{

//Compare comfunc;

//while (child > 0)

//{

//size_t parent = (child - 1) / 2;

//if (comfunc(_con[parent], _con[child]))

//{

//swap(_con[child], _con[parent]);

//child = parent;

////加不加这个parent都可以，因为上面可以再次获取,加了可以方便理解

////parent = (child - 1) / 2;

//}

//else

//{

//break;

//}

//}

//}

//i 为child

//也可以是这样的写法

void adjustup(int child)

{

Compare comfunc;

size_t parent = (child - 1) / 2;

//

// 注意：这里的parent 和child的顺序要和adjustdown的if (comfunc(_con[parent] , _con[child]))比较顺序一致

while (comfunc(_con[parent] , _con[child])) {

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

child = parent;

parent = (child - 1) / 2;

}

}

//i为parent

void adjustdown(int parent)

{

Compare comfunc;

size_t child = 2 * parent + 1;

while (child < _con.size())

{

if (child + 1 < _con.size() && comfunc(_con[child] , _con[child + 1]))

{

++child;

}

if (comfunc(_con[parent] , _con[child]))//注意：这里的parent 和child的顺序要和adjustupwhile (comfunc(_con[parent] , _con[child]))顺序一致

{

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

parent = child;

child = 2 * parent + 1;

}

else

{

break;

}

}

}

void push(const T& x)

{

_con.push_back(x);

adjustup(_con.size() - 1);

}

void pop()

{

std::swap(_con[0], _con[_con.size()-1]);

_con.pop_back();

adjustdown(0);

}

T& top()

{

return _con[0];

}

size_t size()

{

return _con.size();

}

bool empty()

{

return _con.empty();

}

private:

Container _con;

};

}

🚩总结