如何实现一个优先级队列

Issue 欢迎在 Gtihub Issue 中回答此问题: Issue 49

Author 回答者: hx-code

// 封装优先级队列 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;
}
}

Author 回答者: someGenki

基于最大堆实现优先队列

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