堆 (heap) 与优先队列

基础知识

  • 完全二叉树的回顾
    • 父节点的编号存在可计算的关系，因此不需要边存储的信息
    • 可以用连续空间存储
  • 堆的概念
    • 一种基于完全二叉树的结构
    • 大顶堆和小顶堆
      • 大顶堆：任意三元组之间，父节点都大于子节点
      • 小顶堆：任意三元组之间，父节点都小于子节点
      • 堆顶元素为最大值或最小值
  • 堆适合维护集合的最值

堆的基本操作（手撕小顶堆）

  1. class Heap {
  2.     constructor(data) {
  3.         this.data = data;
  4.         this.compartor = (a, b) => a - b;
  5.         this.heapify();
  6.     }
  7.     // 堆的长度
  8.     size() {
  9.         return this.data.length;
  10.     }
  11.     // 初始化小顶堆
  12.     heapify() {
  13.         if (this.size() < 2) return;
  14.         for (let i = 1; i < this.size(); i++) {
  15.             this.bubbleUp(i);
  16.         }
  17.     }
  18.     // 两两交换
  19.     swap(i, j) {
  20.         if (i === j) return;
  21.         [this.data[i], this.data[j]] = [this.data[j], this.data[i]];
  22.     }
  23.     // 获取堆顶元素
  24.     peek() {
  25.         if (!this.size()) return null;
  26.         return this.data[0];
  27.     }
  28.     // 添加元素
  29.     offer(val) {
  30.         this.data.push(val);
  31.         this.bubbleUp(this.size() - 1);
  32.     }
  33.     // 删除元素
  34.     poll() {
  35.         let res = this.data[0];
  36.         this.data[0] = this.data.pop();
  37.         if (this.size()) {
  38.             this.bubbleDown(0);
  39.         }
  40.         return res;
  41.     }
  42.     // 上浮（向上调整）
  43.     bubbleUp(index) {
  44.         while (index) {
  45.             let prentIndex = (index - 1) >> 1;
  47.             if (this.compartor(this.data[index], this.data[prentIndex]) < 0) {
  48.                 this.swap(index, prentIndex);
  49.                 index = prentIndex;
  50.             } else {
  51.                 break;
  52.             }
  53.         }
  54.     }
  55.     // 下沉（向下调整）
  56.     bubbleDown(index) {
  57.         // 获取最大下标，保证不会交换出界
  58.         let lastIndex = this.size() - 1;
  59.         while (index < lastIndex) {
  60.             let leftIndex = index * 2 + 1;
  61.             let rightIndex = index * 2 + 2;
  62.             let findIndex = index;
  63.             if (leftIndex <= lastIndex && this.compartor(this.data[leftIndex], this.data[findIndex]) < 0) {
  64.                 findIndex = leftIndex;
  65.             }
  66.             if (rightIndex <= lastIndex && this.compartor(this.data[rightIndex], this.data[findIndex]) < 0) {
  67.                 findIndex = rightIndex;
  68.             }
  69.             if (index !== findIndex) {
  70.                 this.swap(index, findIndex);
  71.                 index = findIndex;
  72.             } else {
  73.                 break;
  74.             }
  75.         }
  76.     }
  77. }
  78. let arr = [8, 7, 6];
  79. let H = new Heap(arr);
  80. H.offer(9);
  81. H.poll();
  82. console.log(H.data);

经典面试题