priorityqueue

c++实现优先队列

优先队列

优先队列是计算机科学中的⼀类抽象数据类型。优先队列中的每个元素都有各⾃的优先级，优先级最⾼的元素最先得到服务；优先级相同的

元素按照其在优先队列中的顺序得到服务。优先队列往往⽤堆来实现。

典型实现

出于性能考虑，优先队列⽤堆来实现，具有O(logn)时间复杂度的插⼊元素性能，O(n)的初始化构造的时间复杂度。如果使⽤⾃平衡⼆叉查

找树，插⼊与删除的时间复杂度为O(logn)，构造⼆叉树的时间复杂度为O(nlogn)。从计算复杂度的⾓度，优先级队列等价于排序算法。

代码⽰例(详情见代码注释)

#include

usingnamespacestd;

classPriorityQueue

{

private:

int*pArray;

intm_length;

public:

PriorityQueue(intN){

//为后续根节点直接从1开始作准备

pArray=newint[N+1];

m_length=0;

}

intdelMax(){

//⼤根堆第⼀个元素为最⼤

intmax=pArray[1];

//将第⼀个元素和最后⼀个元素交换,并使长度减⼀，即删除最⼤的元素

swap(pArray[1],pArray[m_length--]);

//防⽌对象游离

pArray[m_length+1]=NULL;

//下沉恢复堆的有序性

sink(1);

//返回最⼤的节点值

returnmax;

}

voidinsert(intv){

//将值v插⼊到pArray[1]位置处，所以这⾥⽤的前置++

pArray[++m_length]=v;

//新加⼊的元素上浮

swim(m_length);

}

//判断是否为空

boolisEmpty(){

returnm_length==0;

}

intsize(){

returnm_length;

}

//向上浮

voidswim(intk){

//判断最下层的叶⼦节点值如果⼤于其⽗节点则进⼊循环上浮

while(k>1&&pArray[k]>pArray[k/2]){

//交换⽗节点和⼦节点

swap(pArray[k/2],pArray[k]);

//k数值减⼩继续向上浮

k/=2;

}

}

//向下沉

voidsink(intk){

while(2*k<=m_length)

{

//由于堆的性质⽗节点为k则其左⼦树为2*k即j

intj=2*k;

//这⾥先⽐较左⼦树和右⼦树的⼤⼩，将最⼤的那个键记录下来再和⽗节点⽐较

if(j

//和⽗节点⽐较如果⽗节点⽐最⼤的⼦节点还要⼤，则直接退出循环

if(pArray[k]>pArray[j])break;

//如果⽗节点⽐⼦节点⼩则交换

swap(pArray[k],pArray[j]);

//k值变⼤继续下沉

k=j;

}

}

};

intmain(){

PriorityQueuepq(5);

(2);

(11);

(6);

(1);

(15);

cout<<()<

cout<<()<

cout<<()<

cout<<()<

cout<<()<

return0;

}