如何实现一个优先级队列

// 封装优先级队列 function PriorityQueue() { // 在 PriorityQueue 中重新创建一个类，和 java 中的内部类很相似 function QueueElement(element, priority) { this.element = element; this.priority = priority; } // 封装属性，用数组来存储队列 this.items = [];

// 入队
PriorityQueue.prototype.enQueue = function (element, priority) {
 // 1.创建对象
 var queueElement = new QueueElement(element, priority);
 // 2.判断队列是否为空
 if(this.items.length == 0)
   this.items.push(queueElement);
 else {
   var flag = false;
   for(var i = 0; i< this.items.length; i++){
     if(queueElement.priority < this.items[i].priority){
       this.items.splice(i,0,queueElement);
       flag = true;
       break;
     }
   }
   if(!flag)
     this.items.push(queueElement);
 }
}

// 2.出队
PriorityQueue.prototype.deQueue = function () {
 return this.items.shift();
}

// 3.查看队头元素
PriorityQueue.prototype.front = function() {
 return this.items[0];
}

// 4.判断队列是否为空
PriorityQueue.prototype.isEmpty = function() {
 return this.items.length == 0;
}

// 5.查看队列中元素的个数
PriorityQueue.prototype.size = function() {
 return this.items.length;
}

// 6.将队列元素按字符串格式输出
PriorityQueue.prototype.toString = function() {
 var result = "";
 for(var i = 0; i < this.items.length; i++)
   result += this.items[i].element + "  ";
 return result;
}
}
基于最大堆实现优先队列

class MaxHeap {
constructor(arr = []) {

this.heap = []; // 用数组表示堆结构
arr.forEach((item) => this.add(item));

}

add(value) {

// O(logK) 插入节点值: 放入数组末尾并上浮到合适位置
this.heap.push(value);
this.shiftUp(this.heap.length - 1);

}

pop() {

// O(logK) 提取最大值/堆顶: 提取 heap[0] 并用 heap[-1] 进行代替，然后从顶部开始下沉到合适位置
const max = this.heap[0];
this.swap(0, this.size() - 1);
this.heap.pop();
this.shiftDown(0);
return max;

}

peek() {

// 获取最值/堆顶
return this.heap[0];

}

size() {

// 获取当前堆大小
return this.heap.length;

}

// ↓私有属性↓
swap(index1, index2) {

// 交换节点位置
const temp = this.heap[index1];
this.heap[index1] = this.heap[index2];
this.heap[index2] = temp;

}

parentIndex(index) {

// 获取父节点的位置 (index - 1) / 2 向下取整
return (index - 1) >> 1;

}

leftChildIndex(index) {

// 获取左子节点
return index * 2 + 1;

}

rightChildIndex(index) {

// 获取右子节点
return index * 2 + 2;

}

shiftUp(index) {

// 上浮节点，当前值小于父节点值时停止，使当前堆保持最大堆的性质
let parentIndex = this.parentIndex(index);
while (index > 0 && this.heap[parentIndex] < this.heap[index]) {
  this.swap(index, parentIndex);
  parentIndex = this.parentIndex((index = parentIndex));
}

}

shiftDown(index) {

// 下沉节点，当前值大于子节点值时停止，使当前堆保持最大堆的性质
const leftIndex = this.leftChildIndex(index);
const rightIndex = this.rightChildIndex(index);
//  先比较左子节点值，当前值小于左子节点，则交换,并递归进行下沉
if (this.heap[index] < this.heap[leftIndex]) {
  this.swap(leftIndex, index);
  this.shiftDown(leftIndex);
}
if (this.heap[index] < this.heap[rightIndex]) {
  this.swap(rightIndex, index);
  this.shiftDown(rightIndex);
}

}
}

// ==TEST==
const priorityQueue = new MaxHeap([2, 5, 3]);
console.log(priorityQueue.peek()); // 5
priorityQueue.add(7);
console.log(priorityQueue.peek()); // 7
priorityQueue.pop();
priorityQueue.add(1);
console.log(priorityQueue.peek()); // 5