JavaScript 优先队列代码：支持自定义排序

JavaScript 实现优先队列的代码，自定义排序（最小堆、最大堆都可以），支持数组、矩阵、对象

优先队列

• 具备优先级的先进先出的队列
• 最高级先出
• 堆实现：插入、弹出复杂度 O(logn) 查询复杂度 O(1) 堆排序（初始化）O(nlog(n))

代码

class PriorityQueue {
  constructor (ar, compare = (a, b) => a - b) {
    this.heap = []
    this.size = 0
    this.compare = compare
    while (ar.length) this.push(ar.pop())
  }

  swap (a, b) {
    const tmp = this.heap[a]
    this.heap[a] = this.heap[b]
    this.heap[b] = tmp
  }

  getParentIndex (index) {
    return index - 1 >> 1
  } 

  shiftUp (index) {
    const parentIndex = this.getParentIndex(index)
    if (this.heap[parentIndex] !== void 0 && this.compare(this.heap[parentIndex], this.heap[index]) > 0) {
      this.swap(parentIndex, index)
      this.shiftUp(parentIndex)
    }
  }

  getLeftIndex (index) {
    return (index << 1) + 1
  }

  getRightIndex (index) {
    return (index << 1) + 2
  }

  shiftDown (index) {
    const leftIndex = this.getLeftIndex(index)
    const rightIndex = this.getRightIndex(index)
    if (this.heap[leftIndex] !== void 0 && this.compare(this.heap[index], this.heap[leftIndex]) > 0) {
      this.swap(leftIndex, index)
      this.shiftDown(leftIndex)
    }
    if (this.heap[rightIndex] !== void 0 && this.compare(this.heap[index], this.heap[rightIndex]) > 0) {
      this.swap(rightIndex, index)
      this.shiftDown(rightIndex)
    }
  }

  push (value) {
    this.heap.push(value)
    this.shiftUp(this.size++)
  }

  top () {
    return this.heap[0]
  }

  pop () {
    if (this.size === 0) return null
    if (--this.size === 0) return this.heap.pop()
    const top = this.top()
    this.heap[0] = this.heap.pop()
    this.shiftDown(0)
    return top
  }

  isEmpty () {
    return this.size === 0
  }
}

测试

const minPriorityQueue = new PriorityQueue([5, 3, 2, 1, 4], (a, b) => a - b)
while(!minPriorityQueue.isEmpty()) console.log(minPriorityQueue.pop()) // 1, 2, 3, 4, 5

const maxPriorityQueue = new PriorityQueue([5, 3, 2, 1, 4], (a, b) => b - a)
while(!maxPriorityQueue.isEmpty()) console.log(maxPriorityQueue.pop()) // 5, 4, 3, 2, 1

const priorityQueueWithAlpha = new PriorityQueue(['b', 'c', 'a'], (a, b) => a.charCodeAt() - b.charCodeAt())
while(!priorityQueueWithAlpha.isEmpty()) console.log(priorityQueueWithAlpha.pop()) // a, b, c

const priorityQueueWithMatrix = new PriorityQueue([[2, 'b'], [3, 'c'], [1, 'a']], (a, b) => a[0] - b[0])
while(!priorityQueueWithMatrix.isEmpty()) console.log(priorityQueueWithMatrix.pop())
// [1, 'a'] [2, 'b'] [3, 'c']

const priorityQueueWithObject = new PriorityQueue([{priority: 2, value: 'b'}, {priority: 3, value: 'c'}, (priorityQueueWithObject.pop())
// {priority: 1, value: 'a'} {priority: 2, value: 'b'} {priority: 3, value: 'c'}