164-优先队列—priority_queue

admin管理员组

文章数量:1623796

优先队列—priority_queue

• 优先队列(priority queue)，通常采用堆数据结构来实现。

• 普通的队列是一种先进先出的数据结构，元素在队列尾追加，而从队列头删除。

• 在优先队列中，元素被赋予优先级。当访问元素时，具有最高优先级的元素最先删除。优先队列 具有最高级先出 的行为特征。

• 也就是说它和queue不同的地方就在于我们可以自定义数据的优先级，让优先级高的排在队列前面，优先出队。

1、头文件

#include <queue>

2、定义

priority_queue<Type, Container, Functional>
    Type: 数据类型;
	Container: 容器类型(Container必须是用数组实现的容器，比如vector,deque等等，但不能用 list.STL里面默认用的是vector)
    Functional: 比较的方式，当需要用自定义的数据类型时才需要传入这三个参数，使用基本数据类型时，只需要传入数据类型，默认是大顶堆。(父节点总是大于或等于子节点，这种情况下被叫作大顶堆，或者父节点总是小于或等于子节点，这种情况下叫作小顶堆)
	
    --如果不写后两个参数，那么容器默认用的是vector，比较方式默认用operator<，也就是优先队列是大顶堆，队头元素最大。

常用的大顶堆和小顶堆：

//升序队列——小顶堆
priority_queue <int,vector<int>,greater<int>> pq;
//降序队列——大顶堆
priority_queue <int,vector<int>,less<int>> pq;
 
//greater和less是std实现的两个仿函数（就是使一个类的使用看上去像一个函数。其实现就是类中实现一个operator()，这个类就有了类似函数的行为，就是一个仿函数类了）

优先队列的常用函数有：

    push(elem)   插入元素到队尾(并排序)
    pop()        删除队首元素，但不返回其值
    top()        返回队首元素，但不删除该元素
    empty()      判度队列是否为空，为空返回true，不为空返回false
    size()       返回队列中元素的个数
    emplace(elem)      原地构造一个元素并插入队列

3、优先输出大数据

#include<iostream>
#include<queue>
using namespace std;
 
int main(){
	priority_queue<int> p;	--不写后两个参数，容器默认为vector,大顶堆
	p.push(1);
	p.push(2);
	p.push(8);
	p.push(5);
	p.push(43);
	for(int i=0;i<5;i++){
		cout<<p.top()<<endl;
		p.pop();
	}
	return 0;
}

4、优先输出小数据

方法1：

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

#include<iostream>
#include<queue>
using namespace std;
 
int main(){
	priority_queue<int, vector<int>, greater<int> >p;
	p.push(1);
	p.push(2);
	p.push(8);
	p.push(5);
	p.push(43);
	for(int i=0;i<5;i++){
		cout<<p.top()<<endl;
		p.pop();
	}
	return 0;
}

方法2：

自定义优先级，重载默认的 < 符号 和（）

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

//方法1
struct tmp1 //运算符重载<
{
    int x;
    tmp1(int a) {x = a;}
    bool operator<(const tmp1& a) const
    {
        return x < a.x; //大顶堆
    }
};

//方法2
struct tmp2 //重写仿函数
{
    bool operator() (tmp1 a, tmp1 b) 
    {
        return a.x < b.x; //大顶堆
    }
};

int main() 
{
    tmp1 a(1);
    tmp1 b(2);
    tmp1 c(3);
    priority_queue<tmp1> d;
    d.push(b);
    d.push(c);
    d.push(a);
    while (!d.empty()) 
    {
        cout << d.top().x << '\n';
        d.pop();
    }
    cout << endl;

    priority_queue<tmp1, vector<tmp1>, tmp2> f;
    f.push(c);
    f.push(b);
    f.push(a);
    while (!f.empty()) 
    {
        cout << f.top().x << '\n';
        f.pop();
    }
}

结果：

3
2
1

3
2
1

5、pair数据类型比较

先比较第一个元素，第一个相等比较第二个

#include <iostream>
#include <queue>
#include <vector>
using namespace std;
int main() 
{
    priority_queue<pair<int, int> > a;	--默认是大顶堆
    pair<int, int> b(1, 2);
    pair<int, int> c(1, 3);
    pair<int, int> d(2, 5);
    a.push(d);
    a.push(c);
    a.push(b);
    while (!a.empty()) 
    {
        cout << a.top().first << ' ' << a.top().second << '\n';
        a.pop();
    }
}

2 5
1 3
1 2

6、使用自定义的比较规则来初始化priority_queue

class student{
    public:
        int age;
        string name;
        /**重载小于操作符，
	      *这里必须是非成员函数才可以
		*/
        friend bool operator<(const student& a, const student & b){
            return a.age < b.age;
        }
};

/**可调用的函数操作符的对象*/
struct mycmp{
    bool operator()(const student & a,const student & b){
        return a.age < b.age;
    }
};

/**函数指针*/
bool cmpfunc(const student& a, const student& b){
    return a.age < b.age;
}

/**默认使用student的oprator<来进行比较*/
priority_queue<student> que1;

/**使用重载函数操作符的类对象*/
priority_queue<student,vector<student>,mycmp> que2;

/**定义一下比较函数*/
auto cmp = [](const student & a,const student & b){return a.age < b.age;};
/**
  *	需要把lambda表达式作为优先队列参数进行初始化
  * 并且指定priority_queue的模板实参，decltype(cmp)，c++11 declare type，声明类型
  * 可以认为是确定函数的类型
  * bool (const student & a,const student & b)
  **/
priority_queue<student,vector<student>,decltype(cmp)> que4(cmp);

/*使用函数对象来定义这个比较函数原型*/
//lambda 函数来初始化函数对象
priority_queue<student,vector<student>,function<bool(const student&,const student&)>> que5(cmp);

//函数指针来初始化函数对象
priority_queue<student,vector<student>,function<bool(const student&,const student&)>> que6(cmpfunc);

/**函数对象*/
function<bool(const student&,const student &)> func(cmpfunc);
priority_queue<student,vector<student>,function<bool(const student&,const student&)>> que7(func);

使用案例： 23. 合并K个升序链表

    auto cmp = [](ListNode* a, ListNode* b)->bool {return a->val > b->val; };
    priority_queue<ListNode*, vector<ListNode*>, function<bool(ListNode* a, ListNode* b)>> q(cmp);

class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        if (lists.size() == 0)   return nullptr;

        ListNode* dummy_node = new ListNode(-1);
        ListNode* cur = dummy_node;

        auto cmp = [](ListNode* a, ListNode* b)->bool {return a->val > b->val; };
        priority_queue<ListNode*, vector<ListNode*>, function<bool(ListNode* a, ListNode* b)>> q(cmp);

        for (ListNode* list : lists)
        {
            if (list == nullptr) continue;
            q.push(list);
        }

        while (!q.empty())
        {
            ListNode* temp = q.top();
            q.pop();
            cur->next = temp;
            cur = cur->next;
            if (temp->next != nullptr)
            {
                q.push(temp->next);
            }
        }
        return dummy_node->next;
    }
};

本文标签： 队列priorityqueue