在JS中，我们知道数据类型分为
原始类型（number, string, boolean, null, undefined)
引用类型（object) => Array, function, data, RegExp
原始类型都是保存在栈当中，引用类型都是保存在堆当中
举个例子
var a = 123 // 是原始类型，会在栈底部，创建一个叫做a的房间，里面放入123
var a = 123 // 是原始类型，会在栈底部，创建一个叫做a的房间，里面放入123
var b = a // 再创建一个房间b,将a房间的值copy一份放在b房间
var a = 123 // 是原始类型，会在栈底部，创建一个叫做a的房间，里面放入123
var b = a // 再创建一个房间b,将a房间的值copy一份放在b房间
a = 124 // 再创建一个房间a，里面放入值124，将之前房间a名字删掉，但里面值不删
因为原始值是不可改变的，只会改房间编号，并不会删除房间内的值，所以放在栈中的数据会一直放在底部。就像相机一样，我们删除照片的时候，只是把照片名删掉了，实际内存中还是会存有数据，所以我们要是想销毁数据，就只能大量往内部存照片，覆盖之前的数据就可以了
下面再看堆
var arr = [1, 2] // 会在栈内命名一个arr的房间，但一看值是个引用类型，就会把值放在堆里面，同时arr房间里面存着[1, 2]的房间名
var arr1 = arr // 再在栈内创建一个arr1, 将arr拷贝一份放在arr1房间内，但是，拷贝的只是个引用地址，所以他们都是指向 堆内的[1, 2]
arr.push(3) // 这个时候再往arr push 数据的时候 就是在堆内添加数据，所以arr1也会随之改变
堆（Heap）：堆可以看做是一颗用数组实现的二叉树，所以它没有使用父指针或者子指针。堆根据“堆属性”来排序，“堆属性”决定了树中节点的位置。
特点如下几点：
1.可以使用一维数组来表示。其中，第i个节点的父节点、子节点index如下：
- parent(i) = (i - 1) / 2; (取整)
- leftChild(i) = i * 2 + 1；
- rightChild(i) = i * 2 + 2;
2.堆中某个节点的值总是不大于（最小堆）或不小于（最大堆）其父节点的值
上浮（shiftUp）和下沉（shiftDown）
- 上浮（shiftUp）（以构建最小堆为例）
上浮操作就是，如果一个节点比它父节点小，则将它与父节点交换位置。这个节点在数组中的位置上升。 - 下沉（shiftDown）
下沉操作就是，如果一个节点比它子节点大，那么它需要向下移动。称之为“下沉”。
堆的构建
给定一个一维数组[4,1,3,2,16,9,10,14,8,7]，怎么把它构建成一个堆呢？使用自底向上的方法将数组转化为堆。
大体思路为：如果每一个节点都是一个堆（以这个节点为根），那么这个数组肯定是一个堆。自底向上的方法意思就是，自底向上依次调整每个节点，使得以该节点为根的树是一个堆。
（以最大堆为例）
首先将数组还原成一个完全二叉树
从倒数第一个非叶子节点开始（i = (n/2)-1，其中，n是数组的长度），依次对每个节点执行步骤3，将其调整成最大堆，直至第0个节点。
注：这里要说一下为啥从第一个非叶子节点开始，因为叶节点没有孩子节点，可以把它看成只有一个元素的堆。
将以第i个节点为根节点的子树调整为最大堆。假设根节点A[i]的左右子树的根节点index分别为left[i]和right[i]，其中，left[i]和right[i]都是最大堆。采用逐级下降的方法进行调整，具体步骤如下：
（1） 从A[i]、A[left[i]]、A[right[i]]中找到最大的值，将其下标存到largest中。如果A[i]是最大的，那么以i为根节点的子树是最大堆；否则，交换A[i]和A[largest]的值。
（2） 对下标为largest为根的子树重复（1）操作，直至largest为叶子节点。
如图所示：
从 i = 4 开始遍历，此时，A[4] = 16，它是一个最大堆；
i = 3，A[3] = 2，与A[7]交换，因为i = 7是叶子节点，所以调整完毕。
i = 2，A[2] = 3，与A[6]交换，因为i = 6是叶子节点，所以调整完毕。此时，该树变成：
i = 1，A[1] = 1，与A[4]交换。因为i = 4不是叶子节点，所以要对以4为根的子树进行上述操作；此时，A[4] = 1，与A[9]交换，i = 9是叶子节点，调整完毕。如下图所示：
i = 0，A[0] = 4，与A[1]交换。因为i = 1不是叶子节点，对以1为根的子树进行上述操作；此时，A[1] = 4，与A[3]交换，i = 3不是叶子节点，对以3为根的子树重复进行操作；此时A[3] = 4，与A[8]交换，i = 8是叶子节点，调整完毕。最终得到最大堆：
堆的其它方法
1.插入
向数组最后插入一个数据，然后再向上调整。还以上述数组为例，插入一个11。
在数组最后插入11
比较该节点与其父节点的大小，11 > 7，交换两者，进行上浮。重复该步骤，11 < 14，此时满足最大堆性质，插入完毕。
2.删除（指删除堆顶的数据）
交换堆顶和最后一个数据，删除最后一个数据，再对堆顶数据进行向下调整算法。
交换堆顶和最后一个数据，并删除最后一个数据。
堆根节点进行下沉操作：对比该节点和其左右子节点，将该节点与最大的节点进行交换。重复此操作，直至该节点为叶子节点。（因为这个节点原本就是叶子节点交换上去的，比上面所有层的节点都小，所以调整完毕后，这个节点一定仍是叶子节点）
1与14交换
1与8交换
1与4交换
堆排序
基本思路：
将输入的数组建成最大堆。此时，堆顶元素就是最大值。
交换堆顶元素和末尾元素。此时，末尾元素是最大值。
将剩下 n-1 个元素重新构造成一个堆。重复执行上述步骤。
举个简单的例子：[14, 8, 10, 4]
将该数组构建成最大堆
交换堆顶元素和末尾元素。
忽略末尾元素，将剩下的元素利用下沉法重新构造为一个最大堆。
重复以上步骤，直至剩下的元素只剩下一个。最终得到如下结果，排序完毕：
JavaScript实现堆类
js中并没有“堆”这个数据结构，只能手动实现，以下是源代码。
class MaxHeap {
constructor(heap) {
this.heap = heap;
this.heapSize = heap.length;
this.buildMaxHeap();
}
// 构建最大堆
buildMaxHeap() {
for (let i = Math.floor(this.heapSize / 2) - 1; i >= 0; i--) {
this.maxHeapify(i);
}
}
//将以i为根节点的子树调整为最大堆
maxHeapify(index) {
let left = 2 * index + 1;
let right = 2 * index + 2;
let largest = index;
if (left < this.heapSize && this.heap[left] > this.heap[largest]) largest = left;
if (right < this.heapSize && this.heap[right] > this.heap[largest]) largest = right;
if (largest !== index) {
this.swapNum(index, largest);
this.maxHeapify(largest);
}
}
//交换i，j的值
swapNum(i, j) {
let temp = this.heap[i];
this.heap[i] = this.heap[j];
this.heap[j] = temp;
}
//插入一个数
insert(num) {
this.heap.push(num);
this.heap.heapSize = this.heap.length;
let index = this.heap.heapSize - 1;
while (index != -1) {
index = this.shiftUp(index);
}
console.log(this.heap);
}
//删除堆顶元素
pop() {
this.swapNum(0, this.heapSize - 1);
this.heap.pop();
this.heapSize = this.heap.length;
let index = 0;
while (1) {
let temp = this.shiftDown(index);
if (temp === index) break;
else index = temp;
}
}
//堆排序
heapSort() {
while (this.heapSize > 1) {
this.swapNum(0, this.heapSize - 1);
this.heapSize -= 1;
let index = 0;
while (1) {
let temp = this.shiftDown(index);
if (temp === index) break;
else index = temp;
}
}
this.heapSize = this.heap.length;
}
//上浮操作 - 将当前节点与父节点进行比较，如果该节点值大于父节点值，则进行交换。
shiftUp(index) {
let parent = Math.ceil(index / 2) - 1;
if (this.heap[index] > this.heap[parent] && parent >= 0) {
this.swapNum(index, parent);
return parent;
}
return -1;
}
// 下沉操作 - 将当前节点与左右子节点进行比较，如果该节点值不是最大，则进行交换
shiftDown(index) {
let left = Math.floor(index * 2) + 1;
let right = left + 1;
let largest = index;
if (left < this.heapSize && this.heap[left] > this.heap[largest]) largest = left;
if (right < this.heapSize && this.heap[right] > this.heap[largest]) largest = right;
if (largest !== index) {
this.swapNum(index, largest);
}
return largest;
}
}
