经典算法实现之优先级队列

Hoshea Zhang2023-11-082023-11-09

介绍

队列具有先进先出的特性，添加元素只能在队尾插入，删除只能删除队首元素。

优先级队列出队只能是队列中优先级最高的元素，而不是队首的元素。

出队后优先级队列需要重新维护。

因此，优先级队列和堆很类似。

优先级队列的定义

1 2	template <class T, class Container = vector<T>, class Compare = less<typename Container::value_type> > class priority_queue;

//不写后面两个参数默认为vector，less
priority_queue<int> pq1;
//建立一个优先级队列(大堆)，数据类型是int，利用vector容器实现，less（降序）实现
priority_queue<int, vector<int>, less<int>> pq2;
//建立一个优先级队列(小堆)，数据类型是int，利用vector容器实现，greater（降序）实现
priority_queue<int, vector<int>, greater<int>> pq3;

基本操作

top()

返回元素中第一个元素的引用
push()

插入一个元素，重新维护堆
pop()

删除优先级最高的元素，重新维护堆
size()

返回容器中有效元素的大小
empty()

判空

代码示例：

int main()
{
	//不写后面两个参数默认为vector，less
	priority_queue<int> pq1;
 
	//push的使用
	pq1.push(1);
	pq1.push(2);
	pq1.push(3);
	pq1.push(4);
	pq1.push(5);
	//push完之后，维护也完毕，此时优先级最高的是元素是5，排在第一位
 
	cout << pq1.top() << endl;//优先级最高的一位，所以应该是5
 
	//pop的使用：删除一个优先级最高的元素5，此时重新调整，优先级最高的元素应该为4
	pq1.pop();
	cout << pq1.top() << endl;
 
	//size()的使用,删除了一个元素，此时应该还有四个元素
	cout << pq1.size() << endl;
 
 
	return 0;
}

执行结果：

重写仿函数支持自定义数据类型

仿函数是通过重载()运算符来模拟

class Data
{
public:
	Data(int i, int d)
		:id(d)
		, data(d)
	{}
	int GetData() const
	{
		return data;
	}
private:
	int id;
	int data;
};
//仿函数，从小到大排序，既大的优先级最高
class cmp
{
public:
	bool operator() (Data& d1, Data& d2)
	{
		return d1.GetData() < d2.GetData();
	}
};
int main()
{
    //首先创建三个data类型数据
	Data* d1 = new Data(0, 1);
	Data* d2 = new Data(0, 2);
	Data* d3 = new Data(0, 3);
 
    //创建优先级队列，比较函数为cmp仿函数，并将数据全部push
	priority_queue<Data,vector<Data>,cmp> pq;
	pq.push(*d1);
	pq.push(*d2);
	pq.push(*d3);
    
    //全部输出出来
	while(!pq.empty())
	{
		cout << (pq.top().GetData()) << endl;
		pq.pop();
	}
	return 0;
}

模拟实现

#pragma once
#include<iostream>
using namespace std;
#include<vector>
namespace pq
{
	template<class T, class Container = vector<T>, class Compare = std::less<T>>
	class priority_queue
	{
	public:
		priority_queue()
		{}
		template <class Inputinterpreator>
		priority_queue(Inputinterpreator first, Inputinterpreator last)
		{
			while (first != last)
			{
				_con.push_back(*first);
				++first;
			}
			for (int i = (_con.size() - 1 - 1) / 2; i >= 0; --i)
			{
				adjust_down(i);
			}
		}
		void adjust_up(size_t child)
		{
			Compare com;
			size_t parent = (child - 1) / 2;
			while (child > 0)
			{
				if (com(_con[parent], _con[child]))
				{
					std::swap(_con[child], _con[parent]);
				}
				else
				{
					break;
				}
				child = parent;
				parent = (child - 1) / 2;
			}
		}
		void push(const T& x)
		{
			_con.push_back(x);
			adjust_up(_con.size() - 1);

		}
		void adjust_down(size_t parent)
		{
			Compare com;
			size_t child = (parent * 2) + 1;
			while (child < _con.size())
			{
				if (child + 1 < _con.size() && com(_con[child], _con[child + 1]))
				{
					child = child + 1;
				}
				if (com(_con[parent], _con[child]))
				{
					std::swap(_con[parent], _con[child]);
				}
				else
				{
					break;
				}
				parent = child;
				child = (parent * 2) + 1;
			}
		}
		void pop()
		{
			std::swap(_con[0], _con[_con.size() - 1]);
			_con.pop_back();

			adjust_down(0);
		}
		const T& top()
		{
			return _con[0];
		}
		bool empty()  const
		{
			return _con.empty();
		}
		size_t size() const
		{
			return _con.size();
		}

	private:
		Container _con;
	};
}

其实就是堆排序的思路

int main(){
    pq::priority_queue<int> q;
    q.push(1);
    q.push(2);
    q.push(3);
    cout<<q.top()<<endl;
    q.pop();
    cout<<q.top()<<endl;
    q.pop();
    cout<<q.top()<<endl;
    q.pop();
}

例题

给定整数数组 nums 和整数 k，请返回数组中第 **k** 个最大的元素。

请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        priority_queue<int> pq;
        for(auto n:nums){
            pq.push(n);
        }
        while(k>1){
            pq.pop();
            k--;
        }
        return pq.top();
    }
};