堆

概念

堆通常是一个可以被看做一棵树的数组对象。

堆的实现通过构造二叉堆，实为二叉树的一种。这种数据结构具有以下性质。

  • 任意节点小于（或大于）它的所有子节点
  • 堆总是一棵完全树。即除了最底层，其他层的节点都被元素填满，且最底层从左到右填入。

将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆。

优先队列也完全可以用堆来实现，操作是一模一样的。

实现大根堆

堆的每个节点的左边子节点索引是 i * 2 + 1，右边是 i * 2 + 2，父节点是 (i - 1) /2。

堆有两个核心的操作，分别是 shiftUp 和 shiftDown 。前者用于添加元素，后者用于删除根节点。

shiftUp 的核心思路是一路将节点与父节点对比大小，如果比父节点大，就和父节点交换位置。

shiftDown 的核心思路是先将根节点和末尾交换位置，然后移除末尾元素。接下来循环判断父节点和两个子节点的大小，如果子节点大，就把最大的子节点和父节点交换。

堆 - 图1

  1. class MaxHeap {
  2.   constructor() {
  3.     this.heap = []
  4.   }
  5.   size() {
  6.     return this.heap.length
  7.   }
  8.   empty() {
  9.     return this.size() == 0
  10.   }
  11.   add(item) {
  12.     this.heap.push(item)
  13.     this._shiftUp(this.size() - 1)
  14.   }
  15.   removeMax() {
  16.     this._shiftDown(0)
  17.   }
  18.   getParentIndex(k) {
  19.     return parseInt((k - 1) / 2)
  20.   }
  21.   getLeftIndex(k) {
  22.     return k * 2 + 1
  23.   }
  24.   _shiftUp(k) {
  25.     // 如果当前节点比父节点大，就交换
  26.     while (this.heap[k] > this.heap[this.getParentIndex(k)]) {
  27.       this._swap(k, this.getParentIndex(k))
  28.       // 将索引变成父节点
  29.       k = this.getParentIndex(k)
  30.     }
  31.   }
  32.   _shiftDown(k) {
  33.     // 交换首位并删除末尾
  34.     this._swap(k, this.size() - 1)
  35.     this.heap.splice(this.size() - 1, 1)
  36.     // 判断节点是否有左孩子，因为二叉堆的特性，有右必有左
  37.     while (this.getLeftIndex(k) < this.size()) {
  38.       let j = this.getLeftIndex(k)
  39.       // 判断是否有右孩子，并且右孩子是否大于左孩子
  40.       if (j + 1 < this.size() && this.heap[j + 1] > this.heap[j]) j++
  41.       // 判断父节点是否已经比子节点都大
  42.       if (this.heap[k] >= this.heap[j]) break
  43.       this._swap(k, j)
  44.       k = j
  45.     }
  46.   }
  47.   _swap(left, right) {
  48.     let rightValue = this.heap[right]
  49.     this.heap[right] = this.heap[left]
  50.     this.heap[left] = rightValue
  51.   }
  52. }