二叉堆详解

一、什么是二叉堆

二叉堆是完全二叉树或者是近似完全二叉树，它分为两个类型：

• 最大堆
• 最小堆

最大堆是指任何一个父节点的值，都大于等于它左右孩子节点的值；最小堆是指任何一个父节点的值，都小于等于它左右孩子节点的值

二、二叉堆的自我调整

1.插入节点

我们以下面的最小堆为例，插入元素

新插入的元素为0，将新元素置于二叉堆最后一个位置

我们让新元素与它的父节点比较，如果新元素小于父节点，则与父节点交换位置，否则调整结束

新元素0与父节点5比较，0小于5，0与5交换位置

新元素0继续与父节点2比较，0小于2，0与2交换位置

新元素0继续与父节点1比较，0小于1，0与1交换位置

新元素0到了堆顶的位置，调整结束

2.删除节点

我们同样以前面的二叉堆为例，进行删除元素，删除堆顶元素1

我们将最后一个元素10补到堆顶

接下来，我们将补到堆顶的元素10与它的左右孩子比较，若同时小于左右孩子，则调整结束，否则与左右孩子中较小的一个交换位置

10分别与2、3比较，10大于2、3，2是左右孩子中较小的一个，10与2交换位置

10继续与左右孩子4、5比较，10大于4、5，4是左右孩子中较小的一个，10与4交换位置

10继续与左右孩子8、9比较，10大于8、9，8是左右孩子中较小的一个，10与8交换位置

此时元素10已无孩子节点，调整结束

3.构建二叉堆

构建二叉堆，就是把一个无序的完全二叉树调整为二叉堆，本质上就是让所有非叶子节点依次下沉

我们以下面无序的完全二叉树进行调整，构建二叉堆

我们先找到最后一个非叶子节点3，将它与它的左右孩子比较，若同时小于左右孩子，则该叶子节点调整结束，否则与左右孩子中较小的一个交换位置

3与1比较，3大于1，3与1交换位置

接着比较下一个非叶子节点7，7大于孩子节点2、4，其中2是较小的孩子节点，7与2交换位置

接着比较下一个非叶子节点8，8同时小于孩子节点9、10，不需要交换位置

继续比较下一个非叶子节点6，6大于孩子节点1、2，其中1是较小的孩子节点，6与1交换位置

交换后，6还有孩子节点3，6与3比较，6大于孩子节点3，6与3交换位置

接着比较最后一个非叶子节点5，5与孩子节点1、8比较，5大于1，5与1交换位置

5继续与孩子节点2、3比较，5大于2、3，其中2是较小的孩子节点，5与2交换位置

5继续与孩子节点7、4比较，5大于4，5与4交换位置

自此，二叉堆的构建完成

三、代码实现

二叉堆的所有节点都存在数组中，若父节点的下标是parent，则左右孩子节点的下标分别为2parent+1，2parent+2

// 上浮调整
function upAdjust(arr) {
    let childIndex = arr.length - 1;
    let parentIndex = parseInt((childIndex - 1) / 2);

    // 缓存子节点的值，用于最后进行赋值，而不需要每一步进行交换
    let temp = arr[childIndex];
    while (childIndex > 0 && temp < arr[parentIndex]) {
        arr[childIndex] = arr[parentIndex];
        childIndex = parentIndex;
        parentIndex = parseInt((childIndex - 1) / 2);
    }
    arr[childIndex] = temp;
}

// 下沉调整
function downAdjust(arr, parentIndex, length) {
    // 缓存父节点的值，用于最后进行赋值，而不需要每一步进行交换
    let temp = arr[parentIndex];
    // 孩子节点下标，暂时定为左孩子节点下标
    let childIndex = 2 * parentIndex + 1;

    while (childIndex < length) {
        // 当存在右孩子节点，且右孩子节点的值小于左孩子节点的值，childIndex记录为右孩子节点的下标
        // childIndex实际记录的是最小的孩子节点的下标
        if (childIndex + 1 < length && arr[childIndex + 1] < arr[childIndex]) {
            childIndex++;
        }

        // 如果父节点的值比孩子节点的值都小，则调整结束
        if (temp <= arr[childIndex]) {
            break;
        }

        // 将最小的孩子节点的值赋值给父节点
        arr[parentIndex] = arr[childIndex];
        parentIndex = childIndex;
        childIndex = 2 * parentIndex + 1;
    }
    arr[parentIndex] = temp;
}

function buildHeap(arr) {
    // 从最后一个非叶子节点开始下沉调整
    for (let i = parseInt(arr.length / 2) - 1; i >= 0; i--) {
        downAdjust(arr, i, arr.length);
    }
}

let arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 0];
upAdjust(arr);
console.log(arr);

arr = [5, 6, 8, 7, 3, 10, 9, 2, 4, 1];
buildHeap(arr);
console.log(arr);