本文主要介绍如何使用最大堆的数据结构实现优先级队列。1.优先队列介绍对于普通队列，数据元素是先进先出，而对于优先队列，出队顺序和入队顺序与优先级无关，其特点是动态选择优先级最高的出队.1.1完全二叉树图将元素按顺序排列成树状1.2最大堆图二叉堆是一棵完全二叉树，堆中节点的值总是不大于其父节点的值，从而定义最大Heap：Tips：索引从i=1开始，左子节点索引left(i)=2*i，右子节点right(i)=2*i+1，parent节点prent(i)=i/2整数；Tips：如果索引从i=0开始，左子left(i)=2*i+1，右子right(i)=2*i+2，parent(i)=(i-1)/2四舍五入;1.3向堆中添加元素的SiftUp操作如果新添加的元素大于父节点元素，则需要将新添加的元素节点向上浮动（siftup），交换父节点和子节点的位置，依此类推，交换后继续比较父节点元素的大小。如果儿子比父亲元素大，交换过程示意图如下：1.4从堆中取出最大的元素。取出后，可以将堆中的最后一个元素推到堆顶，然后与子节点进行比较。如果小于子节点元素，堆顶元素需要下沉（SiftDown），交换父节点和子节点的位置。以此类推，继续比较交换后子节点元素的大小，则交换过程示意图如下：1.5优先级队列复杂度的简单比较对于普通的线性结构，enqueue的时间复杂度操作被视为O(1)，出队的时间复杂度被视为O(n)，而对于顺序线性结构，入队操作的时间复杂度被视为O(n)，出队的时间复杂度被视为作为O(1)。对于最大堆，入队操作的时间复杂度为O(logn)，出队操作的时间复杂度为O(logn)。综上所述，使用堆数据结构来实现优先级队列是比较合理的。2.代码实现2.1MaxHeap这是一个基于数组的最大堆，其中add($e)表示向堆中添加元素，siftUp()方法表示向上筛选元素，getMax()方法表示取出堆中最大的元素，siftDown()方法代表下沉元素：array=newArrayStruct($capacity);}/***返回堆中元素的数量*@returnint*/publicfunctiongetSize():int{return$this->array->getSize();}/***判断堆是否为空*@returnbool*/publicfunctionisEmpty():bool{return$this->array->isEmpty();}/***计算一个索引$i节点父节点索引值$iparent+1=($i+1)/2rounded，即$iparent=($i-1)/2rounded*@param$i*@returnint*/privatefunctionparent($i):int{if($i==0){echo"索引0没有父节点";出口;}返回(int)(($i-1)/2);}/***计算一个索引$i节点左子节点索引值$ileft+1=($i+1)*2四舍五入，即$ileft=2*$i+1*@param$i*@returnint*/privatefunctionleftSon($i):int{返回$i*2+1;}/***计算某索引$i节点右子节点索引值$iright+1=($i+1)*2+1rounded,即$ileft=2*$i+2*@param$i*@returnint*/私有函数rightSon($i):int{return$i*2+2;}/***添加到堆中的元素*@param$e*/publicfunctionadd($e):void{$this->array->addLast($e);$this->siftUp($this->array->getSize()-1);}/***元素向上浮动*@param$i*/privatefunctionsiftUp($i){while($i>0&&$this->array->get($this->parent($i))<$this->array->get($i)){$this->swsp($i,$this->parent($i));}$i=$this->parent($i);}}/***元素下沉*@param$i*/privatefunctionsiftDown($i){while($i<$this->array->getSize()&&($this->array->get($this->leftSon($i))>$this->array->get($i)||$this->array->get($this->rightSon($i))>$this->array->get($i))){if($this->array->get($this->leftSon($i))<$this->array->get($this->rightSon($i))){$this->swsp($i,$this->rightSon($i));$i=$this->rightSon($i);}else{$this->swsp($i,$this->leftSon($i));$i=$this->leftSon($i);}}}/***查看堆中最大的元素*@returnmixed*/publicfunctionfindMax(){if($this->array->isEmpty()){echo"堆是空的";出口;}返回$this->array->get(0);}publicfunctiongetMax(){$max=$this->findMax();//删除操作if($this->array->getSize()>1){$this->array->set(0,$this->array->removeLast());$this->siftDown(0);}返回$max;}/***交换堆中的元素值*/publicfunctionswsp($i,$parentI){$parentE=$this->array->get($parentI);$e=$this->array->get($i);$this->array->set($i,$parentE);$this->array->set($parentI,$e);}publicfunctiontoString(){return$this->array->toString();}}2.2ArrayStruct数组类这是一个数组类，可以实现基本数组元素的增删改查操作，动态扩展：capacity=$capacity;}/***获取数组元素个数*@returnint*/publicfunctiongetSize():int{return$this->size;}/***获取数组的容量*@returnint*/publicfunctiongetCapacity():int{return$this->capacity;}/***判断数组是否为空*@returnbool*/publicfunctionisEmpty():bool{return$this->size==0;}/***向数组的指定位置插入一个元素*@paramint$index*@param$e*@throwsException*/publicfunctionadd(int$index,$e):void{if($this->size==$this->capacity){$this->resize(2);//扩展到原来大小的2倍}if($index<0||$index>$this->size){echo"添加的位置超出了数组的大小";出口;}//为了便于理解，[1,2,4,5,6]，假设$index=3;$e=100，在插入[1,2,4,100,5,6]for($i=$this->size;$i>=$index;$i--){$this->data[$i]=$this->data[$i-1];}$this->data[$index]=$e;$这个->尺寸++；}publicfunctionset($index,$e){if($index<0||$index>$this->size){echo"添加的位置超出了数组的范围";出口;}$this->data[$index]=$e;}/***添加一个元素到数组的末尾*@param$e*@throwsException*/publicfunctionaddLast($e):void{$this->add($this->size,$e);}/***在数组的开头插入一个元素*@param$e*@throwsException*/publicfunctionaddFirst($e):void{$this->add(0,$e);}/***获取索引位置数组元素*@paramint$index*@returnmixed*/publicfunctionget(int$index){if($index<0||$index>$this->size){echo"索引值超出元素的位置范围,";出口;}返回$this->data[$index];}/***获取数组末尾的元素*@returnmixed*/publicfunctiongetLast(){return$this->get($this->size-1);}/***获取数组的起始元素*@returnmixed*/publicfunctiongetFirst(){return$this->get(0);}/***判断数组中是否存在某个元素*@param$e*@returnbool*/publicfunctioncontains($e):bool{for($i=1;$i<$this->size;$i++){if($this->data[$i]==$e){返回真；}}返回假；}/***检查数组中某个元素的位置索引值，如果不存在则返回-1*@param$e*@returnint*/publicfunctionfind($e):int{for($i=0;$i<$this->size;$i++){if($this->data[$i]==$e){返回$i;}}返回-1；}/***删除数组中指定位置的元素，返回删除元素的值*@param$index*@returnmixed*/publicfunctionremove($index){if($index<0||$index>$this->size){echo"索引值超出元素的位置范围,";出口;$e=$this->data[$index];对于($i=$index;$i<$this->size-1;$i++){$this->data[$i]=$this->data[$i+1];}$this->size--;$this->data[$this->size]=null;//游荡的物体！=memory/**如果当前数组大小小于容量的一半，重新分配一半数组空间**/if($this->size<=$this->capacity/4&&$this->容量%2==0){$this->resize(0.5);}返回$e;}/***删除数组第一个元素，返回删除元素的值*/publicfunctionremoveFirst(){return$this->remove(0);}/***删除数组的第一个元素并返回删除元素的值*/publicfunctionremoveLast(){return$this->remove($this->size-1);}/***删除数组中的特定元素*@param$e*/publicfunctionremoveElement($e){for($i=0;$i<$this->size;$i++){if($this->data[$i]==$e){$this->remove($i);$this->removeElement($e);休息;}}}/***数组扩容，如果是其他语言，比如JAVA，这里需要重新开空间*@param$factor*/protectedfunctionresize($factor){$this->c容量=$factor*$this->容量；}/***将数组转换为字符串*@returnstring*/publicfunctiontoString():string{$str="[";对于($i=0;$i<$this->size;$i++){$value_str=is_numeric($this->data[$i])?$this->data[$i]:"'{$this->data[$i]]}'";$str.=$i.“=>”。$value_str。",";}$str=trim($str,",");$str.="]";返回$str;}}代码仓库：https://gitee.com/love-for-po...扫码关注爱因世贤
