Skip to main content

优先级队列

用途#

优先级队列这种数据结构有一个很有用的功能, 在插入或者删除元素的时候, 元素会自动排序, 这底层的原理就是二叉堆的操作.

经典案例#

  • 登机时经济舱的普通队列与头等舱的优先级队列
  • 股票交易时基于时间和价格的成交规则上, 量大优先的优先级队列

实现(最大堆)#

该大顶堆接受两种参数, type PriorityQueueElement<T> = number | [number, T], 要么只接收数字当作比较的 key, 要么接受 [key, val] 的形态.

type PriorityQueueElement<T> = number | [number, T]
export class PriorityQueue<T> {  private heap: PriorityQueueElement<T>[] = []
  constructor(initData?: PriorityQueueElement<T>[]) {    if (initData) {      this.build(initData)    }  }
  private build(initData: PriorityQueueElement<T>[]) {    initData.forEach((data) => this.offer(data))  }
  private leftChild(idx: number) {    return idx * 2 + 1  }
  private rightChild(idx: number) {    return idx * 2 + 2  }
  private parentIdx(idx: number) {    return Math.floor((idx - 1) / 2)  }
  private swap(i: number, j: number) {    const tmp = this.heap[i]    this.heap[i] = this.heap[j]    this.heap[j] = tmp  }
  private heapify(idx: number) {    const left = this.leftChild(idx)    const right = this.rightChild(idx)    let smallest = idx
    if (Array.isArray(this.heap[smallest])) {      // if the left child is bigger than the node we are looking at      if (        left < this.heap.length &&        this.heap[smallest][0] < this.heap[left][0]      ) {        smallest = left      }
      // if the right child is bigger than the node we are looking at      if (        right < this.heap.length &&        this.heap[smallest][0] < this.heap[right][0]      ) {        smallest = right      }    } else {      // if the left child is bigger than the node we are looking at      if (left < this.heap.length && this.heap[smallest] < this.heap[left]) {        smallest = left      }
      // if the right child is bigger than the node we are looking at      if (right < this.heap.length && this.heap[smallest] < this.heap[right]) {        smallest = right      }    }
    // if the value of smallest has changed, then some swapping needs to be done    // and this method needs to be called again with the swapped element    if (smallest !== idx) {      this.swap(smallest, idx)      this.heapify(smallest)    }  }
  public size() {    return this.heap.length  }
  public offer(e: PriorityQueueElement<T>) {    // push element to the end of the heap    this.heap.push(e)
    // the idx of the element we have just pushed    let idx = this.heap.length - 1
    // if the element is greater than its parent:    // swap element with its parent
    if (Array.isArray(e)) {      while (        idx !== 0 &&        this.heap[idx][0] > this.heap[this.parentIdx(idx)][0]      ) {        this.swap(idx, this.parentIdx(idx))        idx = this.parentIdx(idx)      }    } else {      while (idx !== 0 && this.heap[idx] > this.heap[this.parentIdx(idx)]) {        this.swap(idx, this.parentIdx(idx))        idx = this.parentIdx(idx)      }    }  }
  public peek() {    // the root is always the highest priority item    return this.heap[0]  }
  public poll() {    // remove the first element from the heap    const root = this.heap.shift()
    // put the last element to the front of the heap    // and remove the last element from the heap as it now    // sits at the front of the heap    this.heap.unshift(this.heap[this.heap.length - 1])    this.heap.pop()
    // correctly re-position heap    this.heapify(0)
    return root  }}