优先队列

优先队列是一种抽象数据类型

前言

请结合二叉堆一起看

应用场景

• 模拟系统：事件的键为发生时间，系统按时间顺序处理事件
• 任务调度：键值对应优先级，决定先处理哪些任务
• 数值计算：键值代表计算错误，按照键值指定的顺序来修正他们

API

• delMax() 删除最大的元素
• insert() 插入元素

用例

public class MaxPQ<Key extends Comparable<Key>> {
      MaxPQ(key[] a)
      void insert(Key v)
    Key max()
    Key delMax()
    Boolean isEmpty()
    int size()
}

基于二叉堆的优先队列

import { exch, less, swin, sink } from './util'; 
class MaxPQ <Key extends Comparable<Key>> {
  private pq: Array<number | string>;
  private N: number;
  constructor(maxN) {
    this.pq = new Array(maxN + 1);
    this.N = maxN;
  }
  public isEmpty(): boolean {
    return this.N === 0;
  }
  public size(): number {
    return this.N;
  }
  public insert(v): void {
    this.pq[++N] = v;
    swin(N)
  }
  public delMax(v): void {
    const max = this.pq[1];
    exch(1, N--);
    this.pq.pop();
    sink(1);
    return max;
  }
}