堆

最小堆

最小堆（Min Heap）实现

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

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

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

    // 获取堆的最小值（堆顶）
    peek() {
        return this.isEmpty() ? undefined : this.heap[0];
    }

    // 插入元素
    insert(value) {
        this.heap.push(value);
        this.bubbleUp(this.size() - 1);
    }

    // 移除堆顶（最小值）
    extract() {
        if (this.isEmpty()) return undefined;
        const min = this.heap[0];
        const last = this.heap.pop();
        if (!this.isEmpty()) {
            this.heap[0] = last;
            this.sinkDown(0);
        }
        return min;
    }

    // 上浮调整
    bubbleUp(index) {
        while (index > 0) {
            const parentIndex = Math.floor((index - 1) / 2);
            if (this.heap[parentIndex] <= this.heap[index]) break;
            [this.heap[parentIndex], this.heap[index]] = [this.heap[index], this.heap[parentIndex]];
            index = parentIndex;
        }
    }

    // 下沉调整
    sinkDown(index) {
        const left = 2 * index + 1;
        const right = 2 * index + 2;
        let smallest = index;

        if (left < this.size() && this.heap[left] < this.heap[smallest]) {
            smallest = left;
        }
        if (right < this.size() && this.heap[right] < this.heap[smallest]) {
            smallest = right;
        }
        if (smallest !== index) {
            [this.heap[index], this.heap[smallest]] = [this.heap[smallest], this.heap[index]];
            this.sinkDown(smallest);
        }
    }
}



//添加value的比较，可以随时替换value，以匹配比较对象
class MinHeap {
    constructor() {
        this.heap = [];
    }

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

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

    // 获取堆的最小值（堆顶）
    peek() {
        return this.isEmpty() ? undefined : this.heap[0];
    }

    // 插入元素
    insert(value) {
        this.heap.push(value);
        this.bubbleUp(this.size() - 1);
    }

    // 移除堆顶（最小值）
    extract() {
        if (this.isEmpty()) return undefined;
        const min = this.heap[0];
        const last = this.heap.pop();
        if (!this.isEmpty()) {
            this.heap[0] = last;
            this.sinkDown(0);
        }
        return min;
    }

    // 上浮调整
    bubbleUp(index) {
        while (index > 0) {
            const parentIndex = Math.floor((index - 1) / 2);
            if (this.heap[parentIndex] &&this.heap[parentIndex].value <= this.heap[index].value) break;
            [this.heap[parentIndex], this.heap[index]] = [this.heap[index], this.heap[parentIndex]];
            index = parentIndex;
        }
    }

    // 下沉调整
    sinkDown(index) {
        const left = 2 * index + 1;
        const right = 2 * index + 2;
        let smallest = index;

        if (left < this.size() &&this.heap[left]&& this.heap[left].value < this.heap[smallest].value) {
            smallest = left;
        }
        if (right < this.size() &&this.heap[right]&& this.heap[right].value < this.heap[smallest].value) {
            smallest = right;
        }
        if (smallest !== index) {
            [this.heap[index], this.heap[smallest]] = [this.heap[smallest], this.heap[index]];
            this.sinkDown(smallest);
        }
    }
}

最大堆

最大堆（Max Heap）实现

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

    size() {
        return this.heap.length;
    }

    isEmpty() {
        return this.size() === 0;
    }

    peek() {
        return this.isEmpty() ? undefined : this.heap[0];
    }

    insert(value) {
        this.heap.push(value);
        this.bubbleUp(this.size() - 1);
    }

    extract() {
        if (this.isEmpty()) return undefined;
        const max = this.heap[0];
        const last = this.heap.pop();
        if (!this.isEmpty()) {
            this.heap[0] = last;
            this.sinkDown(0);
        }
        return max;
    }

    bubbleUp(index) {
        while (index > 0) {
            const parentIndex = Math.floor((index - 1) / 2);
            if (this.heap[parentIndex] >= this.heap[index]) break;
            [this.heap[parentIndex], this.heap[index]] = [this.heap[index], this.heap[parentIndex]];
            index = parentIndex;
        }
    }

    sinkDown(index) {
        const left = 2 * index + 1;
        const right = 2 * index + 2;
        let largest = index;

        if (left < this.size() && this.heap[left] > this.heap[largest]) {
            largest = left;
        }
        if (right < this.size() && this.heap[right] > this.heap[largest]) {
            largest = right;
        }
        if (largest !== index) {
            [this.heap[index], this.heap[largest]] = [this.heap[largest], this.heap[index]];
            this.sinkDown(largest);
        }
    }
}