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'}