c++ priority_queue用法

1 priority_queue的定义

基本定义方法：

基本定义默认是使用大顶堆的，即队首总是最大的元素

priority_queue<int> q;//储存int型数据 
priority_queue<double> q;//储存double型数据 
priority_queue<string> q;//储存string型数据 
priority_queue<结构体名> q;//储存结构体或者类

快速切换大小顶堆定义：

less<储存的数据类型> 即使用大顶堆

greater<储存的数据类型> 即是用小顶堆

priority_queue<储存的类型,vector<储存的类型>,顶堆的类型> 容器名

eg:

使用大顶堆的队列

priority_queue<int,vector<int>,less<int>> q;//储存int型数据 
priority_queue<double,vector<double>,less<double>> q;//储存double型数据 
priority_queue<string,vector<string>,less<string>> q;//储存string型数据 
priority_queue<结构体名,vector<结构体名>,less<结构体名>> q;//储存结构体或者类

使用小顶堆的队列

priority_queue<int,vector<int>,greater<int>> q;//储存int型数据
priority_queue<double,vector<double>,greater<double>> q;//储存double型数据
priority_queue<string,vector<string>,greater<string>> q;//储存string型数据
priority_queue<结构体名,vector<结构体名>,greater<结构体名>> q;//储存结构体或者类

使用结构体重载运算符定义：

priority_queue<int,vector<int>,cmp> q;//储存int型数据 
priority_queue<double,vector<double>,cmp> q;//储存double型数据 
priority_queue<string,vector<string>,cmp> q;//储存string型数据
priority_queue<结构体名,vector<结构体名>,cmp> q;//储存结构体或者类

2 priority_queue的成员函数

empty() 如果优先队列为空，则返回真 
pop() 删除第一个元素 
push() 加入一个元素 
size() 返回优先队列中拥有的元素的个数 
top() 返回优先队列中有最高优先级的元素

3 重载

函数重载

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

struct Test {
    int val;
    Test(int v) : val(v) {}
};

// 自定义比较函数
bool compare(const Test& t1, const Test& t2) {
    return t1.val < t2.val;
}

int main() {
    // 定义一个优先级队列，使用自定义的比较函数
    priority_queue<Test, vector<Test>, decltype(&compare)> pq(&compare);

    // 插入一些元素
    pq.push(Test(3));
    pq.push(Test(1));
    pq.push(Test(5));
    pq.push(Test(2));

    // 输出队列中的元素
    while (!pq.empty()) {
        cout << pq.top().val << " ";
        pq.pop();
    }
    cout << endl;

    return 0;
}

decltype它的作用是从变量或表达式的类型中推导出类型，并在这里用于获取比较函数的类型以传递给 priority_queue。如果你知道比较函数的类型，也可以直接在模板参数中指定该类型，而不必使用 decltype。

class Solution {
public:
    // 假设这里有其他方法和成员函数

    ListNode* mergeKLists(vector<ListNode*>& lists) {
        priority_queue<ListNode*, vector<ListNode*>, bool (*)(ListNode*, ListNode*)> pq(compare); // 直接指定比较函数的类型
        // 将 lists 中的元素依次压入优先队列
        for (ListNode* node : lists) {
            if (node != nullptr) {
                pq.push(node);
            }
        }

        ListNode* dummy = new ListNode(0);
        ListNode* current = dummy;

        // 从优先队列中取出最小元素，并将其后续节点压入队列，直到队列为空
        while (!pq.empty()) {
            ListNode* topNode = pq.top();
            pq.pop();
            current->next = topNode;
            current = current->next;
            if (topNode->next != nullptr) {
                pq.push(topNode->next);
            }
        }

        return dummy->next;
    }
};

bool (*)(ListNode*, ListNode*) 是一个函数指针类型，它表示指向一个接受两个 ListNode* 类型参数并返回 bool 类型值的函数的指针。在这个上下文中，它用来指定优先级队列中元素比较的函数类型。

具体解释如下：

bool 表示函数的返回类型为布尔值，用于表示比较结果的真假。
(*ptr) 表示这是一个指针。
(ListNode*, ListNode*) 表示函数接受两个 ListNode* 类型的参数。

因此，bool (*)(ListNode*, ListNode*) 表示指向一个接受两个 ListNode* 参数并返回布尔值的函数的指针类型。

结构体重载

#include<iostream>//c++标准头文件，可以使用cout,cin等标准库函数 
#include<queue>//使用priority_queue时需要的头文件 
using namespace std;//命名空间，防止重名给程序带来各种隐患，使用cin,cout,stack,map,set,vector,queue时都要使用
struct test{//定义一个结构体test 
	int val;
	test(int v){//构造函数 
		this->val=v;
	}
//	下面是基本的运算方法，我们不能随意更改它 
	bool operator > (const test t)const{//重载运算符
		return val>t.val;
	}
	bool operator < (const test t)const{//重载运算符
		return val<t.val;
	}
};

struct cmp{
	bool operator () (const test t1,const test t2)const{//重载括号运算符
		return t1.val<t2.val;//小于号是大根堆，大于号是小根堆 
	}
};
int main(){
	priority_queue<test,vector<test>,cmp> q;//自定义一个优先级队列q 
	cout<<"自定义一个优先级队列q: priority_queue<test,vector<test>,cmp> q"<<endl; 
	q.push(test(10));//向队列中添加一个test，val的值为10 
	q.push(test(5));//向队列中添加一个test，val的值为5
	q.push(test(7));//向队列中添加一个test，val的值为7
	cout<<"q.top().val="<<q.top().val<<endl;
	cout<<endl; 
	
	
	q.pop();
	cout<<"q.top().val="<<q.top().val<<endl;
	cout<<endl; 
	
	q.pop();
	cout<<"q.top().val="<<q.top().val<<endl;
	cout<<endl; 
	
	q.pop();
	cout<<"目前队列是空的，不能使用q.top()查询队首元素"<<endl;
	
	
}