admin管理员组文章数量:1623792
一.什么是优先级队列
首先要注意的就是别与队列(queue)搞混了,队列是一种先进先出(First in First out,FIFO)的数据类型。每次元素的入队都只能添加到队列尾部,出队时从队列头部开始出。
优先级队列(priority_queue)其实,不满足先进先出的条件,更像是数据类型中的“堆”。优先级队列每次出队的元素是队列中优先级最高的那个元素,而不是队首的元素。这个优先级可以通过元素的大小等进行定义。比如定义元素越大优先级越高,那么每次出队,都是将当前队列中最大的那个元素出队。
详细介绍:priority_queue - C++ Reference (cplusplus) (官方网站)
优先级队列的定义:
简单理解:
priority_queue<typename, container, functional>
typename是数据的类型;
container是容器类型,可以是vector,queue等用数组实现的容器,不能是list,默认用的vector;
functional是比较的方式,默认是大顶堆(就是元素值越大,优先级越高);如果使用C++基本数据类型,可以直接使用自带的less和greater这两个仿函数(默认使用的是less,就是构造大顶堆,元素小于当前节点时下沉)。使用自定义的数据类型的时候,可以重写比较函数,也可以在自定义类型中进行运算符重载(less重载小于“<”运算符,构造大顶堆;greater重载大于“>”运算符,构造小堆)。
说到这里,大家应该都知道了,优先级队列的底层就是堆,所有需要用到堆的位置,都可以考虑使用priority_queue。注意:默认情况下priority_queue是大堆
常用接口:
优先级队列的简单使用:
215. 数组中的第K个最大元素 - 力扣(LeetCode)
给定整数数组 nums
和整数 k
,请返回数组中第 k
个最大的元素。
class Solution {
public:
int findKthLargest(vector<int>& nums, int k)
{
priority_queue<int> q1(nums.begin(),nums.end());
while(--k)
{
q1.pop();
}
return q1.top();
}
};
是不是就很简单。
二.如何模拟实现一个优先级队列
我们前面谈到过了,优先级队列的底层就是堆。故把建堆这个大工程搞定就会轻松很多很多。
在我们实现的优先级队列中,模板的定义如下:template<class T,class Container = vector<T>,class comper=Less<T>>,这里我们自己实现了仿函数 :
这里可能有人会问了,什么是仿函数:
仿函数(Functor)是一种行为类似于函数的对象,可以像函数一样被调用。仿函数是一个类或结构体,它重载了圆括号操作符 "()",因此可以像函数一样被调用。像是一个可调用的函数,但它实际上是一个类或结构体。你可以像调用函数一样来使用它,传入参数并获得返回值
template <class T>
class Less
{
public:
bool operator()(const T& x, const T& y)
{
return x < y;
}
};
template<class T>
class Greater
{
public:
bool operator()(const T& x, const T& y)
{
return x > y;
}
};
建堆
建堆,我们就要想到两种算法。向上调整算法,向下调整算法。
备注:因为默认的容器时vector,故这里再模拟的时候也是vector,_con其实是vector<类型>_con
向上调整算法O(N*logN):
简单来说,向上调整算法是当你插入一个元素时,它是从叶子节点逐步向父亲节点比较,直到根节点。
void AdjustUp(int child)
{
comper com;
int parent = (child - 1) / 2;
while (child > 0)
{
if (com(_con[parent], _con[child]))
{
swap(_con[child], _con[parent]);
child = parent;
parent = (child - 1) / 2;
}
else
{
break;
}
}
}
向下调整算法O(N):
void AdjustDown(int parent)
{
comper com;
int child = parent * 2 + 1;//假设左孩子大
while (child<_con.size())
{
//判断右孩子是否存在,并找最大发的哪一个孩子
if (child + 1 < _con.size() && com(_con[child], _con[child + 1]))
//if (child + 1 < _con.size() && _con[child] < _con[child + 1])
{
child++;
}
if (com(_con[parent], _con[child]))
{
swap( _con[parent],_con[child]);
parent=child;
child= parent * 2 + 1;
}
else
{
break;
}
}
}
因为向下调整的时间复杂度要小,故建堆的时候我们通常采用向下调整算法。这个算法是通过parent来找child的,故需要parent。而在vector中,我们如何找parent?
for (size_t i = (_con.size() - 1 - 1)/2; i >=0; i--)
{
AdjustDown(i);//向下调整算法,建大堆
}
_con.size()-1是找到下标(child),根据公式,parent=(child-1)/2来找到。
建堆完成后,其他功能的实现就很简单。
pop与push:
注意:在pop时,不能直接删除。要先将第一个和最后一个元素交换,再删除最后一个位置,然后为了保持原来的大堆/小堆结构,再走一次向下调整算法。
void pop()//堆顶元素
{
swap(_con[0], _con[_con.size() - 1]);
_con.pop_back();
AdjustDown(0);
}
注意:push也不能只插入到里面就不管,为了防止破坏原来的结构,则需要走一次向上调整算法。
void push(const T& x)
{
_con.push_back(x);
AdjustUp(_con.size() - 1);
}
其他功能接口:
因为容器的类型时vector,所以判断empty,size时,可以直接调用vector的接口:
bool empty()
{
return _con.empty();
}
size_t size()
{
return _con.size();
}
再模拟实现的priority_queue中,top接口如何实现呢?其实很简单,它就是vector的第一个元素。
三.完整代码:
//仿函数
//仿函数(Functor)是一种行为类似于函数的对象,可以像函数一样被调用。仿函数是一个类或结构体,它重载了圆括号操作符 "()",因此可以像函数一样被调用。
//仿函数就像是一个可调用的函数,但它实际上是一个类或结构体。你可以像调用函数一样来使用它,传入参数并获得返回值
template <class T>
class Less
{
public:
bool operator()(const T& x, const T& y)
{
return x < y;
}
};
template<class T>
class Greater
{
public:
bool operator()(const T& x, const T& y)
{
return x > y;
}
};
namespace dnx
{
template<class T,class Container = vector<T>,class comper=Less<T>>
class priority_queue
{
private:
void AdjustDown(int parent)
{
comper com;
int child = parent * 2 + 1;//假设左孩子大
while (child<_con.size())
{
//判断右孩子是否存在,并找最大发的哪一个孩子
if (child + 1 < _con.size() && com(_con[child], _con[child + 1]))
//if (child + 1 < _con.size() && _con[child] < _con[child + 1])
{
child++;
}
if (com(_con[parent], _con[child]))
{
swap( _con[parent],_con[child]);
parent=child;
child= parent * 2 + 1;
}
else
{
break;
}
}
}
void AdjustUp(int child)
{
comper com;
int parent = (child - 1) / 2;
while (child > 0)
{
if (com(_con[parent], _con[child]))
{
swap(_con[child], _con[parent]);
child = parent;
parent = (child - 1) / 2;
}
else
{
break;
}
}
}
public:
//初始化
priority_queue()
{
}
template<class InputIterator>
priority_queue(InputIterator first, InputIterator end)
{
while (first != end)
{
_con.push_back(*first);
first++;
}
//建堆----时间复杂度O(n)
//默认情况下priority_queue是大堆,故我们这里排升序
for (size_t i = (_con.size() - 1 - 1)/2; i >=0; i--)
{
AdjustDown(i);//向下调整算法,建大堆
}
}
void pop()//堆顶元素
{
swap(_con[0], _con[_con.size() - 1]);
_con.pop_back();
AdjustDown(0);
}
void push(const T& x)
{
_con.push_back(x);
AdjustUp(_con.size() - 1);
}
const T& top()
{
return _con[0];
}
bool empty()
{
return _con.empty();
}
size_t size()
{
return _con.size();
}
private:
Container _con;
};
}
四.总结
1.优先级队列默认使用vector作为其底层存储数据的容器,在vector上又使用了堆算法将vector中元素构造成堆的结构。
2.当数据类型是自定义类型的时候,我们可以重写仿函数,或者再自定义类型里面重载"<",">"。
eg:如再日期类里面就重载了小于大于符号,但是如果我的数据类型恰好是日期类对象的地址。
这个时候我们只有重写仿函数(一般的日期类里面咋会有堆解引用的重载,不符合实际应用)。
struct LessPDate
{
bool operator()(const Date* p1, const Date* p2)
{
return *p1 < *p2;
}
};
本文标签: 优先级队列priorityqueue
版权声明:本文标题:优先级队列(priority_queue) 内容由热心网友自发贡献,该文观点仅代表作者本人, 转载请联系作者并注明出处:https://www.elefans.com/dongtai/1728894765a1178268.html, 本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容,一经查实,本站将立刻删除。
发表评论