堆

1.概念

• 特殊的完全二叉树
• 所有节点都大于等于（最大堆）或者小于等于（最小堆）它的子节点

• js 中通常用数组表示堆
  • 左侧节点的位置是 2*index + 1
  • 右侧节点的位置是 2*index + 2
  • 父节点位置是 (index - 1) / 2

2.应用

• 堆能快速高效的找出最大值和最小值，时间复杂度 O(1)
• 找出第 k 个最大(小)元素

第 k 个最大元素

• 构建一个最小堆，并将元素依次插入堆中
• 当堆的容量超过 k,就删除堆顶
• 插入结束后，堆顶就是第 k 个最大元素

js 实现最小堆类

• 在类里声明一个数组，用来装元素
• 主要方法：插入，删除堆顶、获取堆顶、获取堆大小
• 插入
  • 将值插入堆的底部，即数组尾部
  • 然后上移：将这个值和它的父节点交换，直到父节点小于等于这个插入的值
  • 大小为 k 的堆中插入元素的时间复杂度为 O(log k)
• 删除堆顶
  • 用数组尾部元素替换堆顶（直接删除堆顶会破坏堆结构）
  • 然后下移：将新堆顶和它的子节点进行交换，直到子节点大于等于这个新堆项
  • 大小为 k 的堆中插入元素的时间复杂度为 O(log k)
• 获取堆顶
  • 返回数组的头部
• 获取堆的大小
  • 直接返回数组的长度

class MinHeap {
  constructor() {
      this.heap = [];
  }
  swap(i1, i2) {
      const temp = this.heap[i1];
      this.heap[i1] = this.heap[i2];
      this.heap[i2] = temp;
  }
  getParentIndex(i) {
      return (i - 1) >> 1;
  }
  getLeftIndex(i) {
      return i * 2 + 1;
  }
  getRightIndex(i) {
      return i * 2 + 2;
  }
  shiftUp(index) {
      if (index == 0) { return; }
      const parentIndex = this.getParentIndex(index);
      if (this.heap[parentIndex] > this.heap[index]) {
          this.swap(parentIndex, index);
          this.shiftUp(parentIndex);
      }
  }
  shiftDown(index) {
      const leftIndex = this.getLeftIndex(index);
      const rightIndex = this.getRightIndex(index);
      if (this.heap[leftIndex] < this.heap[index]) {
          this.swap(leftIndex, index);
          this.shiftDown(leftIndex);
      }
      if (this.heap[rightIndex] < this.heap[index]) {
          this.swap(rightIndex, index);
          this.shiftDown(rightIndex);
      }
  }
  insert(value) {
      this.heap.push(value);
      this.shiftUp(this.heap.length - 1);
  }
  pop() {
      this.heap[0] = this.heap.pop();
      this.shiftDown(0);
  }
  peek() {
      return this.heap[0];
  }
  size() {
      return this.heap.length;
  }
}
const h = new MinHeap();
h.insert(3);
h.insert(2);
h.insert(1);
h.pop();