题解 | 合并k个已排序的链表

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

    insert(node) {
        this.heap.push(node);
        this.bubbleUp(this.heap.length - 1);
    }

    extractMin() {
        if (this.heap.length === 0) return null;
        if (this.heap.length === 1) return this.heap.pop();

        const minNode = this.heap[0];
        this.heap[0] = this.heap.pop();
        this.bubbleDown(0);

        return minNode;
    }

    isEmpty() {
        return this.heap.length === 0;
    }

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

    bubbleDown(index) {
        const length = this.heap.length;
        while (true) {
            let smallest = index;
            const leftChildIndex = 2 * index + 1;
            const rightChildIndex = 2 * index + 2;

            if (
                leftChildIndex < length &&
                this.heap[leftChildIndex].val < this.heap[smallest].val
            ) {
                smallest = leftChildIndex;
            }

            if (
                rightChildIndex < length &&
                this.heap[rightChildIndex].val < this.heap[smallest].val
            ) {
                smallest = rightChildIndex;
            }

            if (smallest !== index) {
                [this.heap[index], this.heap[smallest]] = [
                    this.heap[smallest],
                    this.heap[index],
                ];
                index = smallest;
            } else {
                break;
            }
        }
    }
}
function mergeKLists(lists) {
    // write code here
    const heap = new MinHeap();

    // 将每个链表的头节点加入最小堆
    for (let i = 0; i < lists.length; i++) {
        if (lists[i]) {
            heap.insert(lists[i]);
        }
    }

    const dummy = new ListNode(0);
    let current = dummy;

    while (!heap.isEmpty()) {
        const node = heap.extractMin();
        current.next = node;
        current = current.next;

        if (node.next) {
            heap.insert(node.next);
        }
    }

    return dummy.next;
}
module.exports = {
    mergeKLists: mergeKLists,
};