二叉堆数据结构

[wl05]

概念

堆是一种特殊的二叉树，也叫做二叉堆

1. 它是一棵完全二叉树
2. 最大（最小）堆是一棵每一个节点的键值都不小于（大于）其孩子（如果存在）的键值的树。

最小堆实现：（最大堆实现类似）

class MinHeap {
    constructor() {
        this.heap = [];
    }

    /**
     * getLeftIndex 获取位置 index左侧子节点的位置
     * @param index
     * @returns {number}
     */
    getLeftIndex(index) {
        return (2 * index) + 1;
    }

    /**
     * getRightIndex 获取位置 index右侧子节点的位置
     * @param index
     * @returns {number}
     */
    getRightIndex(index) {
        return (2 * index) + 2;
    }

    /**
     * getParentIndex 获取位置 index父节点的位置
     * @param index
     * @returns {*}
     */
    getParentIndex(index) {
        if (index === 0) {
            return undefined;
        }
        return Math.floor((index - 1) / 2);
    }

    /**
     * 获取堆的大小
     * @returns {number}
     */
    size() {
        return this.heap.length;
    }

    /**
     * 判断堆是否为空
     * @returns {boolean}
     */
    isEmpty() {
        return this.size() <= 0;
    }

    /**
     * 清空堆
     */
    clear() {
        this.heap = [];
    }

    /**
     * 这个方法返回最小值(最小堆)且不会移除这个值。在最小堆中，最小值总是位于数组的第一个位置(堆的根节点)
     * @returns {undefined}
     */
    findMinimum() {
        return this.isEmpty() ? undefined : this.heap[0];
    }

    /**
     * 这个方法向堆中插入一个新的值。如果插入成功，它返回 true，否 则返回 false。
     * @param value
     * @returns {boolean}
     */
    insert(value) {
        if (value !== null) {
            const index = this.heap.length;
            this.heap.push(value);
            this.siftUp(index);
            return true;
        }
        return false;
    }

    /**
     * 上移操作
     * 表示我们将要将这个值和它的父节点进行交换，直到父节点小于这个插入的值
     * @param index
     */
    siftUp(index) {
        let parent = this.getParentIndex(index);
        while (index > 0 && this.heap[parent] > this.heap[index]) {
            [this.heap[parent], this.heap[index]] = [this.heap[index], this.heap[parent]]
            index = parent;
            parent = this.getParentIndex(index);
        }
    }

    /**
     * 这个方法移除最小值，并返回这个值。
     * 在移除后，我们将堆的最后一个元素移动至根部并执行 siftDown 函数，表示我们将交换元素直到堆的结构正常
     * @returns {*}
     */
    extract() {
        if (this.isEmpty()) {
            return undefined;
        }
        if (this.size() === 1) {
            return this.heap.shift();
        }
        const removedValue = this.heap[0];
        this.heap[0] = this.heap.pop();
        this.siftDown(0);
        return removedValue;
    }

    /**
     * 下移操作
     * 表示将元素和最小子节点进行交换。如果元素 比左侧子节点要小且 index 合法，
     * 我们就交换元素和它的左侧子节点。
     * 如果元素小于它的右侧子节点且 index 合法，我们就交换元素和它的右侧子节点
     * 在找到最小子节点的位置后，我们要检验它的值是否和 element 相同!
     * 如果不是，就将它和最小的 element 交换，并且重复这个过程直到 element 被放在正确的位置上。
     * @param index
     */
    siftDown(index) {
        let element = index;
        const left = this.getLeftIndex(index);
        const right = this.getRightIndex(index);
        const size = this.size();
        if (left < size && this.heap[element] > this.heap[left]) { // 如果有左子节点，并且比左子节点小
            element = left;
        }
        if (right < size && this.heap[element] > this.heap[right]) { // 如果有右子节点，并且比右子节点小
            element = right;
        }
        if (index !== element) { // index === element 说明找到了正确的位置，递归结束
            [this.heap[index], this.heap[element]] = [this.heap[element], this.heap[index]]
            this.siftDown(element);
        }
    }

    getAsArray() {
        return this.heap;
    }
}

const heap = new MinHeap();
heap.insert(2);
heap.insert(3);
heap.insert(4);
heap.insert(5);
heap.insert(1);
heap.insert(10)
console.log('======getAsArray=========')
console.log(heap.getAsArray())
console.log('===============')
console.log('======findMinimum=========')
console.log(heap.findMinimum())
console.log('===============')
console.log('======extract=========')
console.log(heap.extract())
console.log('===============')
console.log('======getAsArray=========')
console.log(heap.getAsArray())
console.log('===============')
console.log('======extract=========')
console.log(heap.extract())
console.log('===============')
console.log('======getAsArray=========')
console.log(heap.getAsArray())
console.log('===============')

参考文章

1. JavaScript实现 简易堆