堆

翻了翻博客，大概在前年的时候，总结过一些数据结构的知识以及使用，但是始终没有发现堆的影子。也是从去年总结到今年的常见算法合集中，遇到需要用堆来解决的算法，一筹莫展。所以将对堆的常规操作做一个总结，以便记忆。

堆的基础概念

堆是一种特殊的树。满足于下列两点要求，他就是一个堆。

1. 堆是一个完全二叉树。
2. 堆中每个节点的值都必须大于等于(小于等于)其子树中每个节点的值。

第一点，堆是完全二叉树。完全二叉树要求，除了最后一层，其他层的节点个数都是满的，且最后一层的节点都靠左排列。 第二点，堆中每个节点的值都必须大于等于(小于等于)其子树中每个节点的值，换种说法，堆中每个节点的值都大于等于(小于等于)其左右子节点的值。

堆可以分为两种。

• 对于每个节点的值都大于等于子树中每个节点的值的堆，叫做大顶堆
• 对于每个节点的值都小于等于子树中每个节点的值得堆，叫做小顶堆。

如何实现一个堆

实现一个堆，首先需要知道堆都支持什么操作以及如何存储一个堆。

堆的存储

堆是一个完全二叉树，用数组来存储完全二叉树是非常节省空间的，可以单纯通过数组的下标就找到一个节点的左右节点以及父节点。

从图中可以看出，数组中下标为 i 的节点，其左节点的下标为 2*i，其右节点的下标为 2*i+1，其父节点的下标为 i/2。

堆操作

插入一个元素

往堆中插入一个元素之后，依旧需要满足堆的两个特性。 需要进行调整以满足对的特性，这个过程叫做堆化。 堆化有两种方法，从下往上和从上往下。

堆化非常简单，就是顺着节点所在路径，向上或者向下对比，然后交换。 分析从下往上的堆化过程。

1. 先把数据插入堆中，然后与其父节点比大小。
2. 如果新节点大于父节点，就交换两个节点。
3. 一直重复这个过程，直到父节点大于等于新节点。

当前过程翻译成为代码，如下：

class MaxHeap {
  constructor() {
    this.data = [0];
  }
  //插入元素
  insertItem(item) {
    this.data.push(item);
    this.__shiftUp(this.getSize());
  }
  //获取堆的大小
  getSize() {
    return this.data.length - 1;
  }
  //向上堆化
  __shiftUp(k) {
    while (k > 1 && this.data[k] > this.data[parseInt(k / 2)]) {
      this.__swap(k, parseInt(k / 2));
      k = parseInt(k / 2);
    }
  }
  //交换元素
  __swap(i, j) {
    [this.data[i], this.data[j]] = [this.data[j], this.data[i]];
  }
}

删除堆顶元素

在堆的定义中，任何节点都大于等于(小于等于)其左右节点的值，由此可得堆顶元素就是堆中数据的最大值(最小值)。 上述代码中，我们构建的是大顶堆，堆顶就是最大元素。 删除思路： 删除堆顶元素之后，把第二大的元素放到堆顶，也就是其左右节点中较大的。迭代删除第二大节点，以此类推，直到叶子节点被删除。 这种方法会有问题，可能最后堆化出来的堆不满足完全二叉树的特性。

1. 为了满足完全二叉树的特性，可以把最后一个节点放到堆顶
2. 使用同样父子节点比较的方式，对于不满足关系的父子节点，交换两个节点
3. 重复这个过程，直到父子关系均满足大小关系

上述步骤就是从上往下堆化法。

当前过程翻译成为代码，如下：

class MaxHeap {
  //删除堆顶
  deleteMax() {
    if (this.getSize() === 0) return -1;
    this.data[1] = this.data.pop();
    this.__shiftDown(this.getSize(), 1);
  }
  //向下堆化
  __shiftDown(len, k) {
    while (true) {
      let maxPos = k;
      if (2 * k <= len && this.data[k] < this.data[2 * k]) maxPos = 2 * k;
      if (2 * k + 1 <= len && this.data[maxPos] < this.data[2 * k + 1])
        maxPos = 2 * k + 1;
      if (k === maxPos) break;
      this.__swap(maxPos, k);
      k = maxPos;
    }
  }
}

如何基于堆实现排序

堆排序的过程大致分为两个步骤：建堆和排序。

建堆

将数组原地组建成一个堆。所谓’原地’就是，不借助另一个数组，在原数组上操作。 建堆有两种思路：

• 在堆中插入一个元素的思路。起初堆中只包含一个数据，就是下标为 1 的数据，调用插入操作，将下标从 2 到 n 的数据依次插入到堆中，采用从下往上堆化的的方式。
• 从后往前处理数组，并且每个数据都是从上往下堆化。

采用第二种思路，叶子节点向下堆化只能和自己本身比较，所以从第一个非叶子节点开始，依次堆化。 在完全二叉树中，小标 n/2+1 到 n 的节点是叶子节点，我们不需要堆化，下标从 1 到 n/2 的数据进行堆化。

function __buildHeap(arr, num) {
  for (let i = parseInt(num / 2); i > 0; i--) {
    __shiftDown(arr, num, i);
  }
}

function __shiftDown(arr, len, k) {
  while (true) {
    let maxPos = k;
    if (2 * k <= len && arr[k] < arr[2 * k]) maxPos = 2 * k;
    if (2 * k + 1 <= len && arr[maxPos] < arr[2 * k + 1]) maxPos = 2 * k + 1;
    if (k === maxPos) break;
    __swap(arr, maxPos, k);
    k = maxPos;
  }
}

function __swap(arr, i, j) {
  [arr[i], arr[j]] = [arr[j], arr[i]];
}

排序

建堆结束之后，数组中的数据都已经按着大顶堆的特性排列。数组中的第一个元素是堆顶，也就是最大的元素。 思路：

1. 我们把它跟最后一个元素交换一下，那么最大的元素就放到下标为 n 的位置。(类似删除堆顶元素)
2. 用堆化的方法，将剩下的 n-1 元素重新构建成堆。
3. 再取堆顶元素，放到下标 n-1 的位置，一直重复这个过程，直到堆中只剩下标为 1 的元素，排序完成。

function sort(arr, num) {
  __buildHeap(arr, num);
  let len = num;
  while (len > 1) {
    __swap(arr, len, 1);
    len--;
    __shiftDown(arr, len, 1);
  }
}

堆排序包括建堆和排序两个操作，建堆的复杂度是 O(n)，堆排序的复杂度是 O(nlogn)，所以整体的复杂度为 O(nlogn)。 堆排序不是稳定的排序算法，因为在排序的过程中，堆嘴后一个元素和堆顶节点交换，可能改变值相同数据原始的相对顺序。

完整代码

总结

堆是一种完全二叉树。最大的特性是：每个节点的值大于等于(小于等于)其子树节点的值。因此分为大顶堆和小顶堆。

堆中最重要的操作是插入数据和删除堆顶数据。插入数据时，把新数据放到最后，从下往上堆化。删除堆顶元素时，把最后一个元素放到堆顶，从上往下堆化。两者的复杂程度都是 O(logn)。

堆排序包含两个过程：建堆和堆化。建堆时，将下标从 n/2 到 1 的节点依次从上到下的堆化操作，然后可以把数组中的数字变成堆这种数据结构。排序时，堆顶的元素放到堆的末尾，并将堆的大小减一，然后再堆化，重复这个过程，直到堆中只剩下一个元素。