什么是堆？

满足下面两个条件的就是堆：

堆是一个完全二叉树（完全二叉树：若设二叉树的深度为h,除第 h 层外,其它各层 (1~h-1) 的结点数都达到最大个数,第 h 层所有的结点都连续集中在最左边,这就是完全二叉树。）
堆上的任意节点值都必须大于等于（大顶堆）或小于等于（小顶堆）其左右子节点值

如果堆上的任意节点都大于等于子节点值，则称为 大顶堆

如果堆上的任意节点都小于等于子节点值，则称为 小顶堆

也就是说，在大顶堆中，根节点是堆中最大的元素；在小顶堆中，根节点是堆中最小的元素；

堆的存储

我们知道，完全二叉树适用于数组存储法（前端进阶算法7：小白都可以看懂的树与二叉树），而堆又是一个完全二叉树，所以它可以直接使用数组存储法存储：也就是说堆其实可以用一个数组表示，给定一个节点的下标 i （i从1开始），那么它的父节点一定为 A[i/2] ，左子节点为 A[2i] ，右子节点为 A[2i+1]**

堆的创建

插入式创建：每次插入一个节点，实现一个大顶堆（或小顶堆）
原地创建：又称堆化，给定一组节点，实现一个大顶堆（或小顶堆）

插入式建堆

插入节点：

将节点插入到队尾
自下往上堆化： 将插入节点与其父节点比较，如果插入节点大于父节点（大顶堆）或插入节点小于父节点（小顶堆），则插入节点与父节点调整位置
一直重复上一步，直到不需要交换或交换到根节点，此时插入完成。

代码如下：

function insert(key) {
    items.push(key)         //push:插入到队尾
    // 获取存储位置
    let i = items.length-1 
    while (i/2 > 0 && items[i] > items[i/2]) {  
        swap(items, i, i/2); // 交换 
        i = i/2; 
    }
}  
function swap(items, i, j) {
    let temp = items[i]
    items[i] = items[j]
    items[j] = temp
}

原地建堆（堆化）

原地建堆的方法有两种：

自下而上式堆化 ：将节点与其父节点比较，如果节点大于父节点（大顶堆）或节点小于父节点（小顶堆），则节点与父节点调整位置
自上往下式堆化 ：将节点与其左右子节点比较，如果存在左右子节点大于该节点（大顶堆）或小于该节点（小顶堆），则将子节点的最大值（大顶堆）或最小值（小顶堆）与之交换

所以，自下而上式堆是调整节点与父节点（往上走），自上往下式堆化是调整节点与其左右子节点（往下走）。

1. 从前往后、自下而上式堆化建堆

这里以小顶堆为例，

代码如下(还是有点不太理解)：

// 原地建堆
function buildHeap(items, heapSize) {
    while(heapSize < items.length-1) {
        heapSize ++
        heapify(items, heapSize)
    }
}

function heapify(items, i) {
    // 自下而上式堆化
    while (Math.floor(i/2) > 0 && items[i] < items[Math.floor(i/2)]) {
        swap(items, i, Math.floor(i/2)); // 交换
        i = Math.floor(i/2);
    }
}

function swap(items, i, j) {
    let temp = items[i]
    items[i] = items[j]
    items[j] = temp
}

// 测试
var items = [,5, 2, 3, 4, 1]
// 初始有效序列长度为 1
buildHeap(items, 1)
console.log(items)
// [empty, 1, 2, 3, 5, 4]

2. 从后往前、自上而下式堆化建堆

这里以小顶堆为例

注意：从后往前并不是从序列的最后一个元素开始，而是从最后一个非叶子节点开始，这是因为，叶子节点没有子节点，不需要自上而下式堆化。

最后一个子节点的父节点为 n/2 ，所以从 n/2 位置节点开始堆化：

代码实现如下：

// 原地建堆
// items: 原始序列
// heapSize: 初始有效序列长度
function buildHeap(items, heapSize) {
    // 从最后一个非叶子节点开始，自上而下式堆化
    for (let i = Math.floor(heapSize/2); i >= 1; --i) {    
        heapify(items, heapSize, i);  
    }
}
function heapify(items, heapSize, i) {
    // 自上而下式堆化
    while (true) {
        var minIndex = i;
        if(2*i <= heapSize && items[i] > items[i*2] ) {
            minIndex = i*2;
        }
        if(2*i+1 <= heapSize && items[minIndex] > items[i*2+1] ) {
            minIndex = i*2+1;
        }
        if (minIndex === i) break;
        swap(items, i, minIndex); // 交换 
        i = minIndex; 
    }
}  
function swap(items, i, j) {
    let temp = items[i]
    items[i] = items[j]
    items[j] = temp
}

// 测试
var items = [,5, 2, 3, 4, 1]
// 因为 items[0] 不存储数据
// 所以：heapSize = items.length - 1
buildHeap(items, items.length - 1)
console.log(items)
// [empty, 1, 2, 3, 4, 5]

注：JavaScript 的存储机制分为代码空间、栈空间以及堆空间，代码空间用于存放可执行代码，栈空间用于存放基本类型数据和引用类型地址，堆空间用于存放引用类型数据，当调用栈中执行完成一个执行上下文时，需要进行垃圾回收该上下文以及相关数据空间，存放在栈空间上的数据通过 ESP 指针来回收，存放在堆空间的数据通过副垃圾回收器（新生代）与主垃圾回收器（老生代）来回收。