TypeScript数据结构与算法：二叉堆

上一篇《TypeScript 数据结构与算法：红黑树》实现了 Typescript 中自平衡的红黑树的数据结构与算法，本篇继续实现二叉堆（Heap）。

二叉堆

二叉堆是一种特殊的二叉树，能高效、快速地找出最大值和最小值，常被应用于优先队列，也被用于著名的堆排序算法中，它有两个特性：

• 结构特性：它是一棵完全二叉树，表示树的每一层都有左侧和右侧子节点（除了最后一层的叶节点），并且最后一层的叶节点尽可能都是左侧子节点。
• 堆特性：二叉堆不是最小堆就是最大堆。最小堆允许你快速提取树的最小值，最大堆允许你快速提取树的最大值。所有的节点都大于等于（最大堆）或小于等于（最小堆）每个它的子节点。

如下图，满足堆有序的完全二叉树，也就是二叉堆：

二叉堆表示法

在之前表示二叉树数据结构时，都是使用的专门的树数据结构，通过引用来指向左右子节点。但是由于二叉堆是个完全二叉树，所以可以使用更简单的数组结构来实现，如下图所示，位置 k 的节点的父节点的位置为 ⌊k/2⌋，而它的两个子节点的位置则分别为 2k 和 2k+1。这样通过计算数组的索引在就可以在树中上下移动：从 a[k] 向上一层就令 k 等于 k/2，向下一层则令 k 等于 2k 或 2k+1。

数据结构实现

交换元素

首先实现一个辅助方法，用于交换数组中的两个元素，使用了 ES6 的解构赋值：

/**
 * @description: 交换数组中的两个位置处的值
 */
export function swap(array: any[], a: number, b: number) {
  [array[a], array[b]] = [array[b], array[a]];
}

二叉堆类

实现一个最小二叉堆 MinHeap 类。最大堆类似，只要将比较函数取反为 reverseCompare 即可。

在类中实现了一些基础方法，比如获取左子节点，右子节点和父节点索引等方法：

import {
  Compare,
  defaultCompare,
  ICompareFunction,
  reverseCompare,
  swap
} from "../util";

// 最小堆类
export class MinHeap<T> {
  protected heap: T[] = [];

  constructor(protected compareFn: ICompareFunction<T> = defaultCompare) {}

  /**
   * @description: 获取左侧子节点的索引
   */
  private getLeftIndex(index: number): number {
    return 2 * index + 1;
  }

  /**
   * @description: 获取右侧子节点的索引
   */
  private getRightIndex(index: number): number {
    return 2 * index + 2;
  }

  /**
   * @description: 获取父节点的索引
   */
  private getParentIndex(index: number): number {
    if (index === 0) {
      return undefined;
    }
    return Math.floor((index - 1) / 2);
  }

  /**
   * @description: 返回堆数组的长度
   */
  size(): number {
    return this.heap.length;
  }

  /**
   * @description: 返回堆是否为空
   */
  isEmpty(): boolean {
    return this.size() <= 0;
  }

  /**
   * @description: 清空堆
   */
  clear() {
    this.heap = [];
  }

  /**
   * @description: 返回堆顶值
   */
  findMinimum(): T {
    return this.isEmpty() ? undefined : this.heap[0];
  }

  /**
   * @description: 返回保存二叉堆数据的数组
   */
  getAsArray() {
    return this.heap;
  }
}

// 最大堆就是将compareFn结果反转即可
export class MaxHeap<T> extends MinHeap<T> {
  constructor(protected compareFn: ICompareFunction<T> = defaultCompare) {
    super(compareFn);
    this.compareFn = reverseCompare(compareFn);
  }
}

上浮

如果由于某些操作，导致堆的某个节点变得比父节点更大，那么我们就需要通过交换它和父节点来修复堆。如果交换后，仍然比祖父节点还大，就继续交换，直到堆的有序状态恢复。如下图所示：

上浮的实现代码如下：

/**
 * @description: 上移的递归方法
 */
private siftUp(index: number): void {
  // 实现的核心就是不断向父节点交换，一直到合适的位置
  let parent = this.getParentIndex(index);
  while (
    index > 0 &&
    this.compareFn(this.heap[parent], this.heap[index]) ===
      Compare.BIGGER_THAN
  ) {
    swap(this.heap, parent, index);
    index = parent;
    parent = this.getParentIndex(index);
  }
}

下沉

同样，如果由于某些操作，导致堆的某个节点变得比子节点更小，那么我们就需要通过交换它和子节点来修复堆。如果交换后，仍然比孙子节点还小，就继续交换，直到堆的有序状态恢复。

但是下沉操作时情况稍微复杂一点，可以选择向左或者向右下沉，毕竟二叉堆是个偏左的完全二叉树，所以原则就是尽量向左下沉，不能向左下沉时再向右下沉。如下图所示：

下沉的实现代码如下：

/**
 * @description: 下移的递归方法
 */
private siftDown(index: number) {
  let element = index;
  // 下移的方法要复杂一些，因为下移要选择左下还是右下
  const left = this.getLeftIndex(index);
  const right = this.getRightIndex(index);
  const size = this.size();

  // 优先向左下移
  if (
    left < size &&
    this.compareFn(this.heap[element], this.heap[left]) ===
      Compare.BIGGER_THAN
  ) {
    element = left;
  }

  // 次之向右下移
  if (
    right < size &&
    this.compareFn(this.heap[element], this.heap[right]) ===
      Compare.BIGGER_THAN
  ) {
    element = right;
  }

  // 交换
  if (index !== element) {
    swap(this.heap, index, element);
    // 继续递归
    this.siftDown(element);
  }
}

插入元素和删除元素

讲完了上浮和下沉，那么具体是什么情况会导致二叉堆的失序呢，其实就是两个操作，插入元素和删除元素。

向二叉堆中插入一个元素时，会先将元素添到数组的最后面，然后根据情况开始上浮。同样，删除元素时，只能删除根节点也就是第一个元素，并把最后一个元素挪到第一个索引处，然后根据情况下沉。

/**
  * @description: 给二叉堆插入一个值，并且调用siftUp方法来上移
  */
insert(value: T): boolean {
  // 校验插入的值
  if (value != null) {
    // 原理就是将插入的值插到最后面，然后逐步向上siftUp，直到合适的位置
    const index = this.heap.length;
    this.heap.push(value);
    // 调用递归siftUp
    this.siftUp(index);
    return true;
  }
  // 如果要插入的值为空，则返回false
  return false;
}

  /**
  * @description: 提取堆顶值，并调用siftDown方法来平衡
  */
extract() {
  if (this.isEmpty()) {
    return undefined;
  }
  if (this.size() === 1) {
    return this.heap.shift();
  }
  const removedValue = this.heap[0];
  this.heap[0] = this.heap.pop();
  this.siftDown(0);
  return removedValue;
}

如此就能实现一个二叉堆。

堆排序

讲完二叉堆的数据结构，再看下堆在排序中的应用。

由于最小堆的根节点始终为其所属树的最小值，所以如果排序一个给定数组时，可以按如下两步操作：

1. 使用改写的下沉方法将给定数组堆化，构造成一个二叉堆；
2. 将二叉堆的根元素（最小值）与最后一个元素交换，然后开始下沉。再将根元素（第二小值）与倒数第二个元素交换，再下沉。不断重复，直到完全排序。

注意：第一步堆化时，由于叶子节点起码占了数组的一半，所以只需要将数组的前一半元素（也就是非叶子节点）下沉即可，

import { Compare, defaultCompare, ICompareFunction, swap } from "../../util";

/**
 * @description: 改造的siftDown方法，多了一个heapSize参数，便于原地排序
 * @param {array} array 要排序的数组
 * @param {number} index 要下沉的元素索引
 * @param {number} heapSize 当前堆的长度（剔除已排序的内容后）
 * @param {ICompareFunction} compareFn 比较大小的方法
 */
function siftDown(
  array: any[],
  index: number,
  heapSize: number,
  compareFn: ICompareFunction<any>
) {
  let largest = index;
  const left = 2 * index + 1;
  const right = 2 * index + 2;

  // 优先向左下移动
  // 与类中siftDown方法最关键的区别就是这个heapSize
  if (
    left < heapSize &&
    compareFn(array[left], array[index]) === Compare.BIGGER_THAN
  ) {
    largest = left;
  }

  // 次之向右下移动
  if (
    right < heapSize &&
    compareFn(array[right], array[largest]) === Compare.BIGGER_THAN
  ) {
    largest = right;
  }

  if (largest !== index) {
    // 交换
    swap(array, index, largest);
    // 继续递归
    siftDown(array, largest, heapSize, compareFn);
  }
}

/**
 * @description: 堆排序
 */
export default function heapSort(array: any[], compareFn = defaultCompare) {
  let heapSize = array.length;

  // 1.首先把除叶子节点外所有的树都规范成二叉堆
  for (let i = Math.floor(array.length / 2); i >= 0; i -= 1) {
    siftDown(array, i, array.length, compareFn);
  }

  // 2.交换堆顶元素和最后的元素，相当于把堆顶元素放到最后面，最后一个元素挪到最前面
  // 然后执行siftDown来重新规范二叉堆
  while (heapSize > 1) {
    swap(array, 0, --heapSize);
    siftDown(array, 0, heapSize, compareFn);
  }
  return array;
}

堆排序已知唯一能够同时最优地利用空间和时间的方法 —— 原地排序并且在最坏的情况下它也能保证使用 O(NlgN) 的时间复杂度。适用于空间十分紧张的嵌入式系统或低成本的移动设备。但它无法利用缓存并且不是稳定排序，所以现代系统很少使用。

下一篇来分析图。

---

前端记事本，不定期更新，欢迎关注！

• 微信公众号： 林景宜的记事本
• 博客：林景宜的记事本
• 掘金专栏：林景宜的记事本
• 知乎专栏： 林景宜的记事本
• Github: MageeLin

---