编辑代码

// 最小堆实现
class MinHeap {
    constructor() {
        this.heap = []
    }

    getLeftIndex(index) {
        return 2 * index + 1
    }

    getRightIndex(index) {
        return 2 * index + 2
    }

    getParentIndex(index) {
        if (index === 0) {
            return undefined
        }
        return Math.floor((index - 1) / 2)
    }

    insert(value) {
        if (value != null) {
            this.heap.push(value);
            this.siftUp(this.heap.length - 1)
            return true;
        }
        return false
    }

    // 上移操作
    siftUp(index) {
        let parent = this.getParentIndex(index);

        // 父节点大于子节点
        // 父子节点就要交换
        while (index > 0 && this.heap[parent] > this.heap[index]) {
            swap(this.heap, parent, index);
            index = parent;
            parent = this.getParentIndex(index)
        }
    }

    // 下移操作
    // 堆化
    // heapify
    siftDown(index) {
        let element = index;
        const left = this.getLeftIndex(index);
        const right = this.getRightIndex(index);
        const size = this.heap.length;

        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) {
            swap(this.heap, index, element);
            this.siftDown(element)
        }
    }

    extract() {
        if (this.heap.length === 0) {
            return undefined
        }

        if (this.heap.length === 1) {
            return this.heap.shift()
        }
        const removedNode = this.heap.shift();
        this.siftDown(0);
        return removedNode
    }
}

function swap(arr, a, b) {
    const temp = arr[a];
    arr[a] = arr[b];
    arr[b] = temp;
}

const heap = new MinHeap();

heap.insert(5)
heap.insert(4)
heap.insert(3)
heap.insert(2)
heap.insert(1)

console.log(heap.heap)