什么是优先队列

优先队列也是一种队列，只不过不同的是，优先队列的出队顺序是按照优先级来的。
优先队列（ADT, Abstract Data Type）是一种数据结构， 支持插入和删除最小/大值操作（返回并删除最小/大元素）。
image.png

对于最小健值元素拥有最高的优先队列， 称之为升序优先队列。
同理， 对于最大健值元素拥有最高的优先队列，称之为降序优先队列。

解决什么问题

需要找到元素集合中的最小或最大元素。

优先队列ADT操作

主要操作

  • 插入
  • 删除
  • 获取

辅助操作

  • 第k小/大
  • 大小
  • 堆排列

优先队列的应用

  • 数据压缩：赫夫曼编码算法
  • 最短路径算法：Dijkstra算法
  • 最小生成树算法：Prim算法
  • 事件驱动仿真：顾客排队算法
  • 选择问题：查找第k个最小元素 拜托，面试别再问我TopK了！！！

练习题集合

堆（大根堆/小根堆）

大根堆：父节点的值比每一个子节点的值都要大。
同理， 小根堆：父节点的值比每一个子节点的值都要小。

  1. class MinHeap {
  2.     constructor(data = []) {
  3.         this.data = data;
  4.         this.comparator = (a, b) => a - b;
  5.         this.heapify();
  6.     }
  7.         // 堆化
  8.     heapify() {
  9.         if (this.size() < 2) return;
  10.         for (let i = 1; i < this.size(); i++) {
  11.                 this.bubbleUp(i);
  12.         }
  13.     }
  15.     peek() {
  16.         if (this.size() === 0) return null;
  17.         return this.data[0];
  18.     }
  20.     offer(value) {
  21.         this.data.push(value);
  22.         this.bubbleUp(this.size() - 1);
  23.     }
  25.     poll() {
  26.         if (this.size() === 0) {
  27.             return null;
  28.         }
  29.         const result = this.data[0];
  30.         const last = this.data.pop();
  31.         if (this.size() !== 0) {
  32.             this.data[0] = last;
  33.             this.bubbleDown(0);
  34.         }
  35.         return result;
  36.     }
  38.     bubbleUp(index) {
  39.         while (index > 0) {
  40.             const parentIndex = (index - 1) >> 1;
  41.             if (this.comparator(this.data[index], this.data[parentIndex]) < 0) {
  42.                 this.swap(index, parentIndex);
  43.                 index = parentIndex;
  44.             } else {
  45.                 break;
  46.             }
  47.         }
  48.     }
  50.     bubbleDown(index) {
  51.         const lastIndex = this.size() - 1;
  52.         while (true) {
  53.             const leftIndex = index * 2 + 1;
  54.             const rightIndex = index * 2 + 2;
  55.             let findIndex = index;
  56.             if (
  57.                 leftIndex <= lastIndex &&
  58.                 this.comparator(this.data[leftIndex], this.data[findIndex]) < 0
  59.             ) {
  60.                 findIndex = leftIndex;
  61.             }
  62.             if (
  63.                 rightIndex <= lastIndex &&
  64.                 this.comparator(this.data[rightIndex], this.data[findIndex]) < 0
  65.             ) {
  66.                 findIndex = rightIndex;
  67.             }
  68.             if (index !== findIndex) {
  69.                 this.swap(index, findIndex);
  70.                 index = findIndex;
  71.             } else {
  72.                 break;
  73.             }
  74.         }
  75.     }
  77.   swap(index1, index2) {
  78.         [this.data[index1], this.data[index2]] = [this.data[index2], this.data[index1]];
  79.     }
  81.     size() {
  82.         return this.data.length;
  83.     }
  84. }

第k个最小元素

var KthLargest = function(k, nums) {
    this.k = k;
    this.heap = new MinHeap();
    for (let num of nums) {
        this.add(num);
    }
};

KthLargest.prototype.add = function(val) {
    this.heap.offer(val);
    if (this.heap.size() > this.k) {
        this.heap.poll();
    }
    return this.heap.peek();
};