堆，特殊的二叉树，也叫作二叉堆。二叉堆能高效、快速地找出最大值和最小值，常被应用于优先队列。也被用于著名的堆排序算法中。

二叉堆的特性

二叉堆是一种特殊的二叉树，有两个特性：结构特性和堆特性。

二叉堆是一棵完全二叉树，表示树的每一层都有左侧和右侧子节点（除了最后一层的叶节点），并且最后一层的叶节点尽可能都是左侧子节点，这叫作结构特性。

二叉堆不是最小堆就是最大堆。最小堆允许快速导出数的最小值，最大堆允许快速导出数的最大值。最小堆所有节点都小于等于它的每个子节点，最大堆所有节点大于等于它的每个子节点。这叫作堆特性。

下图展示了一些合法和不合法的堆：

image.png

虽然二叉堆是二叉树，但是二叉堆并不是二叉搜索树。二叉树节点的左子节点比节点小，而右子节点比节点大，因此二叉搜索树并不满足二叉堆的特性。

二叉树的数组表示

由于二叉堆是一个完全二叉树，因此可以利用数组来表示。下图为一个完全二叉树的数组表示：

图片.png

其中父节点与子节点的关系有：

  • 父节点与左子节点的索引关系为：二叉堆 - 图3，例如索引为 1 的节点，它的左子节点的索引为 二叉堆 - 图4
  • 父节点与右子节点的索引关系为：二叉堆 - 图5，例如索引为 1 的节点，它的右子节点的索引为 二叉堆 - 图6

最小堆的实现

最小堆，父节点比每一个子节点都要小。因此堆顶为这个堆中最小的值。

最小堆有几个方法需要实现：

  • findMinimun：获取堆中的最小值
  • insert：向堆中插入元素
  • extractMinimun：取出堆中的最小值

创建最小堆类

下面的类中，会先列出一些比较常用的方法：

  • 获取左右子节点的索引、获取父节点的索引
  • 交换两个索引位置的元素
  1. interface HeapInterface<E> {
  2.   /** 返回最小值 */
  3.   findMinimun(): E | null;
  4.   /** 向堆中插入一个新的值 */
  5.   insert(value: E): boolean;
  6.   /** 移除最小值（最小堆）*/
  7.   extractMinimun(): E | null;
  8. }
  10. function defaultCompareFunc<E>(a: E, b: E): Compare {
  11.   if (a > b) {
  12.     return Compare.BIGGER_THAN;
  13.   } else if (a < b) {
  14.     return Compare.LESS_THAN;
  15.   } else {
  16.     return Compare.EQUALS;
  17.   }
  18. }
  20. class MinHeap<E> implements HeapInterface<E> {
  21.   heap: E[] = [];
  22.   compareFunc: CompareFunc<E>;
  24.   constructor(compareFunc: CompareFunc<E> = defaultCompareFunc) {
  25.     this.compareFunc = compareFunc;
  26.   }
  28.   /**
  29.    * 获取给定位置 index 节点的左侧子节点的位置
  30.    * @param index
  31.    */
  32.   private getLeftChildIndex(index: number): number {
  33.     const leftChildIndex = 2 * index + 1;
  34.     return leftChildIndex >= this.heap.length ? leftChildIndex : -1;
  35.   }
  37.   /**
  38.    * 获取给定位置 index 节点的右侧子节点的位置
  39.    * @param index
  40.    */
  41.   private getRightChildIndex(index: number): number {
  42.     const rightChildIndex = 2 * index + 2;
  43.     return rightChildIndex >= this.heap.length ? rightChildIndex : -1;
  44.   }
  46.   /**
  47.    * 获取给定位置 index 节点的父节点位置
  48.    * @param index
  49.    */
  50.   private getParentIndex(index: number): number {
  51.     if (index === 0) {
  52.       return -1;
  53.     }
  54.     return Math.floor((index - 1) / 2);
  55.   }
  57.   /**
  58.    * 调换二叉堆 a, b 索引的值
  59.    * @param a
  60.    * @param b
  61.    */
  62.   private swap(a: number, b: number) {
  63.     [this.heap[a], this.heap[b]] = [this.heap[b], this.heap[a]];
  64.   }
  65. }

向堆中插入元素

**
插入元素的操作：

  1. 先将元素插入到堆的尾部
  2. 对元素进行上移操作，元素与父节点进行比较，如果元素比父节点要小，则与父节点互换。直至元素的父节点比元素小为止。
class MinHeap<E> implements HeapInterface<E> {

  // 省略前面的逻辑...

  /**
   * 上移操作
   * 指定节点与父节点进行比较，如果小于父节点，则与父节点交换位置
   * @param index
   */
  private shiftUp(index: number) {
    let parentIndex = this.getParentIndex(index);

    const parentValue = this.heap[parentIndex];
    const value = this.heap[index];

    while (
      index > 0 &&
      this.compareFunc(value, parentValue) === Compare.LESS_THAN
    ) {
      // 当插入值比父节点的值要小的时候，交换两个节点的值
      this.swap(index, parentIndex);
      index = parentIndex;
      parentIndex = this.getParentIndex(index);
    }
  }

  /**
   * 向堆中插入一个新的值
   * @param value
   */
  insert(value: E): boolean {
    if (value === null || value === undefined) {
      return false;
    }
    this.heap.push(value);
    this.shiftUp(this.heap.length - 1);
    return true;
  }
}

取出堆中的最小值

操作：

  1. 由于元素中的第一个元素就是最小值，因此将数组的第一个元素取出
  2. 将堆最后一个元素放到堆顶，然后与左右子节点比较。如果元素比左右子节点都大，那么只要跟左右子节点中最小的节点互换即可。移至元素比左右子节点都小为止。
class MinHeap<E> implements HeapInterface<E> {

  // 省略前面的逻辑...

  /**
   * 下移操作
   * @param index
   */
  private siftDown(index: number): void {
    let element = index;
    const left = this.getLeftChildIndex(index);
    const right = this.getRightChildIndex(index);
    const size = this.size;

    // 判断索引为 element 的值是否比 index 的左子节点的值要小
    if (
      left < size &&
      this.compareFunc(this.heap[element], this.heap[left]) ===
        Compare.BIGGER_THAN
    ) {
      element = left;
    }

    // 判断索引为 element 的值是否比 index 的右子节点的值要小
    // 如果 element 为 left，则是左右子节点的值进行比较
    if (
      right < size &&
      this.compareFunc(this.heap[element], this.heap[right]) ===
        Compare.BIGGER_THAN
    ) {
      element = right;
    }

    if (index !== element) {
      this.swap(index, element);
      this.siftDown(element);
    }
  }

  /** 移除堆中的最小值 */
  extractMinimun(): E | null {
    if (this.isEmpty()) {
      return null;
    }

    if (this.size === 1) {
      return this.heap.shift() as E;
    }

    const removeValue = this.heap.shift() as E;
    this.siftDown(0);

    return removeValue;
  }
}

最大堆的实现

最大堆，父节点比每个子节点都要大。它要实现的方法与最小堆类似：

  • findMax：获取堆中的最大值
  • insert：向堆中插入元素
  • extractMax：取出堆中的最大值

创建最大堆类

最大堆的实现与最小堆的实现非常类似，创建最大堆的类与创建最小堆的类相同，因此可以直接沿用前面创建最小堆的代码。

interface HeapInterface<E> {
  /** 返回最小值 */
  findMax(): E | null;
  /** 向堆中插入一个新的值 */
  insert(value: E): boolean;
  /** 移除最小值（最小堆）*/
  extractMax(): E | null;
}

function defaultCompareFunc<E>(a: E, b: E): Compare {
  if (a > b) {
    return Compare.BIGGER_THAN;
  } else if (a < b) {
    return Compare.LESS_THAN;
  } else {
    return Compare.EQUALS;
  }
}

class MaxHeap<E> implements HeapInterface<E> {
  heap: E[] = [];
  compareFunc: CompareFunc<E>;

  constructor(compareFunc: CompareFunc<E> = defaultCompareFunc) {
    this.compareFunc = compareFunc;
  }

  /**
   * 获取给定位置 index 节点的左侧子节点的位置
   * @param index
   */
  private getLeftChildIndex(index: number): number {
    const leftChildIndex = 2 * index + 1;
    return leftChildIndex >= this.heap.length ? leftChildIndex : -1;
  }

  /**
   * 获取给定位置 index 节点的右侧子节点的位置
   * @param index
   */
  private getRightChildIndex(index: number): number {
    const rightChildIndex = 2 * index + 2;
    return rightChildIndex >= this.heap.length ? rightChildIndex : -1;
  }

  /**
   * 获取给定位置 index 节点的父节点位置
   * @param index
   */
  private getParentIndex(index: number): number {
    if (index === 0) {
      return -1;
    }
    return Math.floor((index - 1) / 2);
  }

  /**
   * 调换二叉堆 a, b 索引的值
   * @param a
   * @param b
   */
  private swap(a: number, b: number) {
    [this.heap[a], this.heap[b]] = [this.heap[b], this.heap[a]];
  }
}

向最大堆中插入元素

插入元素的操作：

  1. 向堆尾部插入元素
  2. 元素与父节点比较大小，如果元素比父节点大则进行交换，直至元素比父节点小为止。
class MaxHeap<E> implements HeapInterface<E> {

  // 省略前面的逻辑...

  /**
   * 上浮 index 索引的元素
   * @param index
   */
  private shiftUp(index: number) {
    if (index < 0 || index > this.data.length) {
      return;
    }

    // 如果父节点比子节点的值小，则进行值的交换
    while (
      index > 0 &&
      this.data[this.getParentIndex(index) as number] < this.data[index]
    ) {
      const parentIndex = this.getParentIndex(index) as number;
      this.swap(parentIndex, index);
      index = parentIndex;
    }
  }

  /**
   * 向二叉堆中添加元素
   * @param e
   */
  insert(e: E): boolean {
    if (e === null || e === undefined) {
      return false;
    }
    this.data.push(e);
    this.shiftUp(this.getSize() - 1);
    return true;
  }
}

取出堆中的最大值

class MaxHeap<E> implements HeapInterface<E> {
  // 省略前面的逻辑...

  /**
   * 元素位置下沉
   * 如果元素比子节点要小，则与最大的子节点进行交换
   * @param index
   */
  private shiftDown(index: number) {
    // 确保节点有左子节点，如果没有左子节点的话，证明已经没有子节点了
    while (this.getLeftChildIndex(index) < this.data.length) {
      // 获取左右子节点的索引
      const leftChildIndex = this.getLeftChildIndex(index);
      const rightChildIndex = this.getRightChildIndex(index);

      // 会被交换值的索引
      let indexWillBeExchange = leftChildIndex;

      // 判断右孩子是否比左孩子大
      if (
        rightChildIndex < this.data.length &&
        this.compareFunc(
          this.data[rightChildIndex],
          this.data[leftChildIndex]
        ) > Compare.BIGGER_THAN
      ) {
        indexWillBeExchange = rightChildIndex;
      }

      if (
        this.compareFunc(this.data[index], this.data[indexWillBeExchange]) ===
        Compare.BIGGER_THAN
      ) {
        const tmp = this.data[index];
        this.data[index] = this.data[indexWillBeExchange];
        this.data[indexWillBeExchange] = tmp;

        index = indexWillBeExchange;
      } else {
        break;
      }
    }
  }

  /** 取出堆中最大元素 */
  extractMax(): E | null {
    const result = this.findMax();

    if (result) {
      // 将数组最后一个元素替换到数组的第一个元素
      this.data[0] = this.data[this.data.length - 1];
      // 删除数组最后一个元素
      this.data.pop();

      this.shiftDown(0);
    }

    return result;
  }
}