本文将通过最大堆实现优先队列，入队复杂度lg(n),出队复杂度lg(n)
step1:实现最大堆
大堆顶定义，每个二叉树的节点都大于左右子节点
class MaxHeap{//构造方法constructor(key) {this._tree=[] //初始化数组保存数据this._key=key //设置排序字段key名}//往队列里添加一个元素，复杂度O(ln(n))add(e){this._tree.push(e) //添加对象到队列末尾this._adaptUp(this._tree.length-1) //自底向上调整最大堆}//获得队首元素值,复杂度O(1)getFront(){return this._tree[0] //返回最大堆顶元素}//获取队首元素值，并弹出队列,复杂度O(ln(n))extractMax(){//交换队尾和和队首元素，并提取队尾元素，避免队列整体移位let tmp=this._tree[0]this._tree[0]=this._tree[this._tree.length-1]this._tree[this._tree.length-1]=tmplet _max=this._tree.pop()this._adaptDown(0) //自顶向下调整最大堆return _max}//获得队列长度getSize(){return this._tree.length}//清空队列clear(){this._tree.clear()}//获得左节点id_leftChild(idx){return idx*2+1}//获得右节点id_rightChild(idx){return idx*2+2}//获得父节点id_parent(idx){return (idx-1)/2|0}//交换队列中两个元素_swap(idx1,idx2){let tmp=this._tree[idx1]this._tree[idx1]=this._tree[idx2]this._tree[idx2]=tmp}//自底向上使堆符合规则_adaptUp(idx){if(idx===0) returnlet parentIdx=this._parent(idx)while (this._tree[idx][this._key]>this._tree[parentIdx][this._key]) { //如果子节点比父节点大，则交换位置this._swap(idx, parentIdx)idx = parentIdxparentIdx = this._parent(idx)}}//自顶向下使堆符合规则_adaptDown(idx){let left=this._leftChild(idx)let right=this._rightChild(idx)let size=this.getSize()let maxPos=leftwhile (idx<size && left<size){ //如果较大子节点大于父节点，则交换位置if(right<size && this._tree[left][this._key]<this._tree[right][this._key]){maxPos=right}if(this._tree[idx][this._key]<this._tree[maxPos][this._key]){this._swap(idx,maxPos)idx=maxPosleft=this._leftChild(idx)right=this._rightChild(idx)maxPos=left}else{break}}}
}
step2:实现优先队列
class PriorityQueue{//构造方法，传入需要排序的keyconstructor(key) {this._data = new MaxHeap(key)}//获得队列长度getSize(){return this._data.getSize()}//获得队首对象getFront(){return this._data.getFront()}//弹出队首元素dequeue(){return this._data.extractMax()}//加入队列enqueue(e){this._data.add(e)}//清空队列clear(){this._data.clear()}//判断队列是否为空isEmpty(){return this._data.getSize()===0}}
step3:例子验证
function test1(){let result=[{name:'李四',age:24},{name:'赵八',age:38},{name:'张三',age:13},{name:'王五',age:25},{name:'吴七',age:27}]let queue=new PriorityQueue("age")//数据加入队列for (let i=0;i<result.length;i++){queue.enqueue(result[i])}//依次弹出队首元素while (!queue.isEmpty()){let obj=queue.dequeue()console.log(obj["name"]+"===="+obj["age"]+"====Queue size=="+queue.getSize())}}test1()
结果展示：
赵八====38====Queue size==4
吴七====27====Queue size==3
王五====25====Queue size==2
李四====24====Queue size==1
张三====13====Queue size==0