【Q048】如何实现一个优先级队列

[shfshanyue]

No description provided.

[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;
}
}

[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