如何构建最小和最大堆("手把手教你构建最小堆和最大堆：从入门到实践")

原创

ithorizon 6个月前 (10-21) 阅读数 33 #后端开发

手把手教你构建最小堆和最大堆：从入门到实践

一、堆的概念及分类

堆（Heap）是一种特殊的树状数据结构，它满足以下性质：

堆是一个完全二叉树；

堆中的每个父节点的值都大于或等于其所有子节点的值（最大堆）；

堆中的每个父节点的值都小于或等于其所有子节点的值（最小堆）。

二、最小堆的构建

最小堆的构建核心有两种方法：向上调整和向下调整。

2.1 向上调整（Shift Up）

向上调整是将一个新元素插入到堆的末尾，然后调整堆以满足最小堆的性质。


function shiftUp(array, index) {
    while (index > 0) {
        let parentIndex = Math.floor((index - 1) / 2);
        if (array[parentIndex] > array[index]) {
            [array[parentIndex], array[index]] = [array[index], array[parentIndex]];
            index = parentIndex;
        } else {
            break;
        }
    }
}

2.2 向下调整（Shift Down）

向下调整是将堆顶元素与最后一个元素交换，然后从堆顶起初调整堆以满足最小堆的性质。


function shiftDown(array, index, length) {
    let leftIndex = 2 * index + 1;
    let rightIndex = 2 * index + 2;
    let smallestIndex = index;
    if (leftIndex < length && array[leftIndex] < array[smallestIndex]) {
        smallestIndex = leftIndex;
    }
    if (rightIndex < length && array[rightIndex] < array[smallestIndex]) {
        smallestIndex = rightIndex;
    }
    if (smallestIndex !== index) {
        [array[index], array[smallestIndex]] = [array[smallestIndex], array[index]];
        shiftDown(array, smallestIndex, length);
    }
}

2.3 构建最小堆

我们可以通过从数组的最后一个非叶子节点起初，向上调整每个节点，从而构建最小堆。


function buildMinHeap(array) {
    let length = array.length;
    for (let i = Math.floor(length / 2) - 1; i >= 0; i--) {
        shiftDown(array, i, length);
    }
    return array;
}

三、最大堆的构建

最大堆的构建方法与最小堆类似，只不过在比较节点值时，最大堆要求父节点的值大于或等于子节点的值。

3.1 向上调整（Shift Up）


function shiftUpMax(array, index) {
    while (index > 0) {
        let parentIndex = Math.floor((index - 1) / 2);
        if (array[parentIndex] < array[index]) {
            [array[parentIndex], array[index]] = [array[index], array[parentIndex]];
            index = parentIndex;
        } else {
            break;
        }
    }
}

3.2 向下调整（Shift Down）


function shiftDownMax(array, index, length) {
    let leftIndex = 2 * index + 1;
    let rightIndex = 2 * index + 2;
    let largestIndex = index;
    if (leftIndex < length && array[leftIndex] > array[largestIndex]) {
        largestIndex = leftIndex;
    }
    if (rightIndex < length && array[rightIndex] > array[largestIndex]) {
        largestIndex = rightIndex;
    }
    if (largestIndex !== index) {
        [array[index], array[largestIndex]] = [array[largestIndex], array[index]];
        shiftDownMax(array, largestIndex, length);
    }
}

3.3 构建最大堆

与构建最小堆类似，从数组的最后一个非叶子节点起初，向上调整每个节点，从而构建最大堆。


function buildMaxHeap(array) {
    let length = array.length;
    for (let i = Math.floor(length / 2) - 1; i >= 0; i--) {
        shiftDownMax(array, i, length);
    }
    return array;
}