STL系列之五 priority_queue 优先级队列

priority_queue 优先级队列是一个拥有权值概念的单向队列queue，在这个队列中，所有元素是按优先级排列的（也可以认为queue是个按进入队列的先后做为优先级的优先级队列——先进入队列的元素优先权要高于后进入队列的元素）。在计算机操作系统中，优先级队列的使用是相当频繁的，进线程调度都会用到。在STL的具体实现中，priority_queue也是以别的容器作为底部结构，再根据堆的处理规则来调整元素之间的位置。下面给出priority_queue的函数列表和VS2008中priority_queue的源代码，本文中与heap有关的函数参见《STL系列之四 heap 堆》。

priority_queue函数列表

函数	描述byMoreWindows(http://blog.csdn.net/MoreWindows)
构造析构
priority_queue <Elem> c	创建一个空的queue 。 注：priority_queue构造函数有7个版本，请查阅MSDN
数据访问与增减
c.top()	返回队列头部数据
c.push(elem)	在队列尾部增加elem数据
c.pop()	队列头部数据出队
其它操作
c.empty()	判断队列是否为空
c.size()	返回队列中数据的个数

可以看出priority_queue的函数列表与栈stack的函数列表是相同的。

VS2008中priority_queue 优先级队列的源代码

友情提示：初次阅读时请注意其实现思想，不要在细节上浪费过多的时间

//VS2008中priority_queue的定义MoreWindows整理(http://blog.csdn.net/MoreWindows)
template<class_Ty,class_Container=vector<_Ty>,class_Pr=less<typename_Container::value_type>>//默认以vector为容器的
classpriority_queue
{//priorityqueueimplementedwitha_Container
public:
typedef_Containercontainer_type;
typedeftypename_Container::value_typevalue_type;
typedeftypename_Container::size_typesize_type;
typedeftypename_Container::referencereference;
typedeftypename_Container::const_referenceconst_reference;

priority_queue():c(),comp()
{//constructwithemptycontainer,defaultcomparator
}

explicitpriority_queue(const_Pr&_Pred):c(),comp(_Pred)
{//constructwithemptycontainer,specifiedcomparator
}

priority_queue(const_Pr&_Pred,const_Container&_Cont):c(_Cont),comp(_Pred)
{//constructbycopyingspecifiedcontainer,comparator
make_heap(c.begin(),c.end(),comp);//参见《STL系列之四heap堆的相关函数》
}

template<class_Iter>
priority_queue(_Iter_First,_Iter_Last):c(_First,_Last),comp()
{//constructbycopying[_First,_Last),defaultcomparator
make_heap(c.begin(),c.end(),comp);
}

template<class_Iter>
priority_queue(_Iter_First,_Iter_Last,const_Pr&_Pred):c(_First,_Last),comp(_Pred)
{//constructbycopying[_First,_Last),specifiedcomparator
make_heap(c.begin(),c.end(),comp);
}

template<class_Iter>
priority_queue(_Iter_First,_Iter_Last,const_Pr&_Pred,const_Container&_Cont):c(_Cont),comp(_Pred)
{//constructbycopying[_First,_Last),container,andcomparator
c.insert(c.end(),_First,_Last);
make_heap(c.begin(),c.end(),comp);
}

boolempty()const
{//testifqueueisempty
return(c.empty());
}

size_typesize()const
{//returnlengthofqueue
return(c.size());
}

const_referencetop()const
{//returnhighest-priorityelement
return(c.front());
}

referencetop()
{//returnmutablehighest-priorityelement(retained)
return(c.front());
}

voidpush(constvalue_type&_Pred)
{//insertvalueinpriorityorder
c.push_back(_Pred);
push_heap(c.begin(),c.end(),comp);
}

voidpop()
{//erasehighest-priorityelement
pop_heap(c.begin(),c.end(),comp);
c.pop_back();
}

protected:
_Containerc;//theunderlyingcontainer
_Prcomp;//thecomparatorfunctor
};

下面先给出优级先级队列的使用范例。

//优先级队列priority_queuebyMoreWindows(http://blog.csdn.net/MoreWindows)
//支持empty()size()top()push()pop()与stack的操作函数全部一样
//byMoreWindows
#include<queue>
#include<list>
#include<cstdio>
usingnamespacestd;
intmain()
{
//优先级队列默认是使用vector作容器。
priority_queue<int>a;
priority_queue<int,list<int>>b;//可以这样声明，但无法使用
inti;
//压入数据
for(i=0;i<10;i++)
{
a.push(i*2-5);
//b.push(i);//编译错误
}
//优先级队列的大小
printf("%d\n",a.size());
//取优先级队列数据并将数据移出队列
while(!a.empty())
{
printf("%d",a.top());
a.pop();
}
putchar('\n');
return0;
}

下面程序是针对结构体的，对数据的比较是通过对结构体重载operator()。

程序功能是模拟排队过程，每人有姓名和优先级，优先级相同则比较姓名，开始有5个人进入队列，然后队头2个人出队，再有3个人进入队列，最后所有人都依次出队，程序会输出离开队伍的顺序。

//byMoreWindows(http://blog.csdn.net/MoreWindows)
#include<queue>
#include<cstring>
#include<cstdio>
usingnamespacestd;
//结构体
structNode
{
charszName[20];
intpriority;
Node(intnri,char*pszName)
{
strcpy(szName,pszName);
priority=nri;
}
};
//结构体的比较方法改写operator()
structNodeCmp
{
booloperator()(constNode&na,constNode&nb)
{
if(na.priority!=nb.priority)
returnna.priority<=nb.priority;
else
returnstrcmp(na.szName,nb.szName)>0;
}
};
voidPrintfNode(Node&na)
{
printf("%s%d\n",na.szName,na.priority);
}
intmain()
{
//优先级队列默认是使用vector作容器，底层数据结构为堆。
priority_queue<Node,vector<Node>,NodeCmp>a;

//有5个人进入队列
a.push(Node(5,"小谭"));
a.push(Node(3,"小刘"));
a.push(Node(1,"小涛"));
a.push(Node(5,"小王"));

//队头的2个人出队
PrintfNode(a.top());
a.pop();
PrintfNode(a.top());
a.pop();
printf("--------------------\n");

//再进入3个人
a.push(Node(2,"小白"));
a.push(Node(2,"小强"));
a.push(Node(3,"小新"));

//所有人都依次出队
while(!a.empty())
{
PrintfNode(a.top());
a.pop();
}

return0;
}

读者可以将上面结构体Node改成类来试下，答案2天后发到本篇的评论中。

转载请标明出处，原文地址：http://blog.csdn.net/morewindows/article/details/6976468