day23-合并k个升序链表

23. 合并 K 个升序链表

给你一个链表数组，每个链表都已经按升序排列。

请你将所有链表合并到一个升序链表中，返回合并后的链表。

示例 1：

输入：lists = [[1,4,5],[1,3,4],[2,6]]
输出：[1,1,2,3,4,4,5,6]
解释：链表数组如下：
[
  1->4->5,
  1->3->4,
  2->6
]
将它们合并到一个有序链表中得到。
1->1->2->3->4->4->5->6

示例 2：

输入：lists = []
输出：[]

示例 3：

输入：lists = [[]]
输出：[]

提示：

• k == lists.length
• 0 <= k <= 10^4
• 0 <= lists[i].length <= 500
• -10^4 <= lists[i][j] <= 10^4
• lists[i] 按 升序 排列
• lists[i].length 的总和不超过 10^4

解法：构建最小堆

class MinHeap{
    constructor() {
        this.heap = [];
    }
    
    // 获取父节点位置
    getParentIndex(index) {
        return Math.floor((index - 1)/2)
    }
    // 获取左侧子节点位置
    getLeftChildIndex(index) {
        return 2 * index + 1
    } 
    // 获取右侧子节点位置
    getRightChildIndex(index) {
        return 2 * index + 2
    }
    // 交换数组中的两个元素
    swap(i,j){
        // 交换数组中的两个元素
        [this.heap[i],this.heap[j]] = [this.heap[j],this.heap[i]]
    }
    // 从当前节点向上堆化
    heapifyUp(index){
        const parentIndex = this.getParentIndex(index)
        if(parentIndex >=0 && this.heap[index].val < this.heap[parentIndex].val){
            // 如果当前节点小于父节点，则交换它们，并继续向上堆化
            this.swap(index,parentIndex)
            this.heapifyUp(parentIndex)
        }
    }

    // 从当前节点向下堆化
    heapifyDown(index){
        const leftChildIndex = this.getLeftChildIndex(index)
        const rightChildIndex = this.getRightChildIndex(index)
        let smallestIndex = index;
        // 如果左子节点小于当前节点，则更新最小值的索引为左子节点的索引
        if(leftChildIndex<this.heap.length && this.heap[leftChildIndex].val < this.heap[smallestIndex].val){
            smallestIndex = leftChildIndex
        }

        // 如果右子节点小于当前节点（及可能更新后的最小值），则更新最小值的索引为右子节点
        if(rightChildIndex < this.heap.length && this.heap[rightChildIndex].val < this.heap[smallestIndex].val){
            smallestIndex = rightChildIndex
        }

        // 如果最小值的索引不是当前节点的索引，则交换它们，并继续向下堆化
        if (smallestIndex !== index) {
            this.swap(index, smallestIndex)
            this.heapifyDown(smallestIndex)
        }

    }

    // 插入元素到堆中
    insert(value) {
        this.heap.push(value)
        this.heapifyUp(this.size() - 1)
    }

    // 提取堆顶的最小值 
    extractMin() {
        if (this.size() === 0) {
            return null
        }
        const minValue = this.heap[0]
        this.heap[0] = this.heap.pop()
        this.heapifyDown(0)
        return minValue
    }
    // 获取堆的大小
    size(){
        return this.heap.length;
    }
    // 弹出堆顶元素 并进行下沉操作保持堆的特性
    pop(){
        if(this.size() === 1) return this.heap.shift();
        const top = this.heap[0];
        this.heap[0] = this.heap.pop();
        this.heapifyDown(0);
        return top;
    }


}

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode[]} lists
 * @return {ListNode}
 */
var mergeKLists = function(lists) {
    const minHeap = new MinHeap();
    const res = new ListNode(0);// 创建虚拟头节点
    let p = res;
    lists.forEach(l => {
        if(l) minHeap.insert(l);
    })
    while(minHeap.size()){
        const n = minHeap.pop();
        p.next = n;
        p = p.next;
        if(n.next) minHeap.insert(n.next);
    }
    return res.next;
};