堆(Heap)

定义

堆通常是一个可以被看做一棵树的数组对象。堆总是满足下列性质：

堆中某个节点的值总是不大于或不小于其父节点的值；
堆总是一棵完全二叉树。

堆的常用方法：

构建优先队列
支持堆排序
快速找出一个集合中的最小值（或者最大值）

将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆。常见的堆有二叉堆、斐波那契堆等。

堆的定义如下：n个元素的序列{k1,k2,ki,…,kn}当且仅当满足下关系时，称之为堆。

(ki <= k2i,ki <= k2i+1)或者(ki >= k2i,ki >= k2i+1), (i = 1,2,3,4...n/2)

若将和此次序列对应的一维数组（即以一维数组作此序列的存储结构）看成是一个完全二叉树，则堆的含义表明，完全二叉树中所有非终端结点的值均不大于（或不小于）其左、右孩子结点的值。由此，若序列{k1,k2,…,kn}是堆，则堆顶元素（或完全二叉树的根）必为序列中n个元素的最小值（或最大值）。

堆和普通树的区别

堆并不能取代二叉搜索树，它们之间有相似之处也有一些不同。我们来看一下两者的主要差别：

节点的顺序。在二叉搜索树中，左子节点必须比父节点小，右子节点必须必比父节点大。但是在堆中并非如此。在最大堆中两个子节点都必须比父节点小，而在最小堆中，它们都必须比父节点大。

内存占用。普通树占用的内存空间比它们存储的数据要多。你必须为节点对象以及左/右子节点指针分配额为是我内存。堆仅仅使用一个数据来村塾数组，且不使用指针。

平衡。二叉搜索树必须是“平衡”的情况下，其大部分操作的复杂度才能达到O(log n)。你可以按任意顺序位置插入/删除数据，或者使用 AVL 树或者红黑树，但是在堆中实际上不需要整棵树都是有序的。我们只需要满足对属性即可，所以在堆中平衡不是问题。因为堆中数据的组织方式可以保证O(log n) 的性能。

搜索。在二叉树中搜索会很快，但是在堆中搜索会很慢。在堆中搜索不是第一优先级，因为使用堆的目的是将最大（或者最小）的节点放在最前面，从而快速的进行相关插入、删除操作。

来自数组的树

用数组来实现树相关的数据结构也许看起来有点古怪，但是它在时间和空间山都是很高效的。

我们准备将上面的例子中的树这样存储：

1	[ 10, 7, 2, 5, 1 ]

就这样！我们除了一个简单的数组以外，不需要任何额外的空间。

可以用堆做什么？

有两个原始操作用于保证插入或删除节点以后堆是一个有效的最大堆或者最小堆：

shiftUp(): 如果一个节点比它的父节点大（最大堆）或者小（最小堆），那么需要将它同父节点交换位置。这样是这个节点在数组的位置上升。
shiftDown(): 如果一个节点比它的子节点小（最大堆）或者大（最小堆），那么需要将它向下移动。这个操作也称作“堆化（heapify）”。

shiftUp 或者 shiftDown 是一个递归的过程，所以它的时间复杂度是 **O(log n)**。

基于这两个原始操作还有一些其他的操作：

insert(value): 在堆的尾部添加一个新的元素，然后使用 shiftUp 来修复对。
remove(): 移除并返回最大值（最大堆）或者最小值（最小堆）。为了将这个节点删除后的空位填补上，需要将最后一个元素移到根节点的位置，然后使用 shiftDown 方法来修复堆。
removeAtIndex(index): 和 remove() 一样，差别在于可以移除堆中任意节点，而不仅仅是根节点。当它与子节点比较位置不时无序时使用 shiftDown()，如果与父节点比较发现无序则使用 shiftUp()。
replace(index, value)：将一个更小的值（最小堆）或者更大的值（最大堆）赋值给一个节点。由于这个操作破坏了堆属性，所以需要使用 shiftUp() 来修复堆属性。

上面所有的操作的时间复杂度都是 **O(log n)**，因为 shiftUp 和 shiftDown 都很费时。还有少数一些操作需要更多的时间：

search(value):堆不是为快速搜索而建立的，但是 replace() 和 removeAtIndex() 操作需要找到节点在数组中的index，所以你需要先找到这个index。时间复杂度：**O(n)**。
buildHeap(array):通过反复调用 insert() 方法将一个（无序）数组转换成一个堆。如果你足够聪明，你可以在 O(n) 时间内完成。
堆排序：由于堆就是一个数组，我们可以使用它独特的属性将数组从低到高排序。时间复杂度：**O(n lg n)**。

堆还有一个 peek() 方法，不用删除节点就返回最大值（最大堆）或者最小值（最小堆）。时间复杂度 O(1) 。

注意：到目前为止，堆的常用操作还是使用 insert() 插入一个新的元素，和通过 remove()移除最大或者最小值。两者的时间复杂度都是**O(log n)**。其其他的操作是用于支持更高级的应用，比如说建立一个优先队列。

实现

const swapData = function (array, index_a, index_b) {
  let temp = array[index_a];
  array[index_a] = array[index_b];
  array[index_b] = temp;
}
const isNumber = function (obj) {
  return typeof obj === 'number' && !isNaN(obj)
}
function Heap(heapArray) {
  this.data = [];
  this.build(heapArray);
}
Heap.prototype.insetValue = function (value) {
  if (isNumber(value)) {
    this.data.push(value);
    this.shiftUp(this.data.length - 1);
  }
}
Heap.prototype.size = function () {
  return this.data.length;
}
Heap.prototype.isEmpty = function () {
  if (this.data.length === 0) {
    return true
  }
  return false;
}
Heap.prototype.getTop = function () {
  return this.data[0] === undefined ? null : this.data[0];
}
Heap.prototype.removeTop = function () {
  let value = undefined;
  if (this.data.length > 1) {
    let value = this.data[0];
    this.data[0] = this.data[this.data.length - 1];
    this.data.pop();
    this.shiftDown(0);
    return value;
  } else if (this.data.length === 1) {
    return this.data.pop();
  } else {
    return null;
  }
}
Heap.prototype.removeAtIndex = function (index) {
  let value = this.data[index];
  this.data[index] = this.data[this.data.length - 1];
  this.data.pop();
  if (this.data[index] > this.data[Math.floor((index - 1) / 2)]) {
    this.shiftUp(index);
  } else if (this.data[index] < this.data[index * 2 + 1]
    || this.data[index] < this.data[index * 2 + 2]) {
    this.shiftDown(index);
  }
  return value;
}
Heap.prototype.shiftUp = function (index) {
  let fatherIndex = Math.floor((index - 1) / 2);
  while (index >= 0) {
    if (this.data[fatherIndex] < this.data[index]) {
      swapData(this.data, fatherIndex, index);
      index = fatherIndex;
      fatherIndex = Math.floor((index - 1) / 2);
    }
    else {
      break;
    }
  }
}
Heap.prototype.shiftDown = function (index) {
  const len = this.data.length;
  let fatherIndex_1 = index * 2 + 1;
  let fatherIndex_2 = index * 2 + 2;

  while (fatherIndex_1 < len || fatherIndex_2 < len) {
    let swapFather = undefined;

    if (this.data[fatherIndex_2] === undefined
      || this.data[fatherIndex_1] > this.data[fatherIndex_2]) {
      swapFather = fatherIndex_1;
    } else {
      swapFather = fatherIndex_2;
    }
    if (this.data[index] < this.data[swapFather]) {
      swapData(this.data, swapFather, index);
      index = swapFather;
      fatherIndex_1 = index * 2 + 1;
      fatherIndex_2 = index * 2 + 2;
    } else {
      break;
    }
  }
}
Heap.prototype.build = function (heapArray) {
  for (let i = 0; i < heapArray.length; i++) {
    this.insetValue(heapArray[i])
  }
}
Heap.isHeap = function (heapArray) {
  const len = heapArray.length;
  for (let i = 0; (2 * i + 2) < len; i++) {
    if (heapArray[i] < heapArray[2 * i + 1] || heapArray[i] < heapArray[2 * i + 2]) {
      return false
    }
  }
  return true;
}

应用

1046. 最后一块石头的重量

有一堆石头，每块石头的重量都是正整数。

每一回合，从中选出两块最重的石头，然后将它们一起粉碎。假设石头的重量分别为 x 和 y，且 x <= y。那么粉碎的可能结果如下：

如果 x == y，那么两块石头都会被完全粉碎；
如果 x != y，那么重量为 x 的石头将会完全粉碎，而重量为 y 的石头新重量为 y-x。
最后，最多只会剩下一块石头。返回此石头的重量。如果没有石头剩下，就返回 0。

示例：

1
2
3

输入:[2,7,4,1,8,1]
输出：1
解释: 最终剩下的石头重量是 1

实现

/**
 * @param {number[]} stones
 * @return {number}
 */
var lastStoneWeight = function (stones) {
  let stoneHeap = new Heap(stones);
  while (true) {
    let stoneFirst = stoneHeap.removeTop();
    if (stoneHeap.isEmpty()) {
      return stoneFirst;
      break;
    }
    let stoneSecond = stoneHeap.removeTop();
    let smallStone = stoneFirst - stoneSecond;
    if (smallStone !== 0) {
      stoneHeap.insetValue(smallStone);
    }
  }
};