数据结构与算法之堆: Leetcode 23. 合并 K 个升序链表 (Typescript版)

合并 K 个升序链表

• https://leetcode.cn/problems/merge-k-sorted-lists/

描述

• 给你一个链表数组，每个链表都已经按升序排列
• 请你将所有链表合并到一个升序链表中，返回合并后的链表

示例 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$

算法实现

1 ）使用堆

/*** Definition for singly-linked list.* class ListNode {*     val: number*     next: ListNode | null*     constructor(val?: number, next?: ListNode | null) {*         this.val = (val===undefined ? 0 : val)*         this.next = (next===undefined ? null : next)*     }* }*/class MinHeap {heap: Array<ListNode | null> = [];// 交换节点位置swap(i1, i2) {[this.heap[i1], this.heap[i2]] = [this.heap[i2], this.heap[i1]];}// 获得父节点getParentIndex(i) {return (i - 1) >> 1;}// 获取左子节点getLeftIndex(i) {return (i << 1) + 1; // 极客写法}// 获取右子节点getRightIndex(i) {return (i << 1) + 2;}// 上移操作封装 是个递归shiftUp(i) {// 如果到了堆顶元素，index是0，则不要再上移了if(!i) return;// 获得父节点下标: piconst pi = this.getParentIndex(i);// 开始做比较if(this.heap[pi]?.val > this.heap[i].val) {// 实现交换this.swap(pi, i);// 继续尝试上移操作this.shiftUp(pi);}}// 下移操作shiftDown(i) {// 如果到了堆尾元素，则不要再下移了if(i >= this.heap.length - 1) return;let li = this.getLeftIndex(i); // 左孩子索引let ri = this.getRightIndex(i); // 右孩子索引// 左孩子节点的值 < 当前节点的值if(this.heap[li]?.val < this.heap[i].val) {this.swap(li, i);this.shiftDown(li);}// 同样，对右孩子节点的值 < 当前节点的值if(this.heap[ri]?.val < this.heap[i].val) {this.swap(ri, i);this.shiftDown(ri);}}// 插入insert(value) {this.heap.push(value);this.shiftUp(this.heap.length - 1);}// 删除堆顶pop() {if(this.size() === 1) return this.heap.shift();let top = this.heap[0];// 变相删除堆顶, 堆尾元素移动到堆顶this.heap[0] = this.heap.pop(); // 删除数组的最后一个元素并返回，返回值赋值给堆顶元素// 执行堆顶下移操作，维持堆的有序性this.shiftDown(0);return top;}// 获取堆顶peak() {return this.heap[0];}// 获取堆的大小size() {return this.heap.length;}
}function mergeKLists(lists: Array<ListNode | null>): ListNode | null {let res = new ListNode(0);let p = res;const h = new MinHeap();// 通过输入来构建堆结构// 三个链表，堆中存入的是三个链表的头lists.forEach(l => {l && h.insert(l); // l是个链表，其实用的是链表头表示，也就是链表的第一个元素})// while循环，每一轮pk的都是堆内的元素// 谁出队，就把谁的下一个入堆，逐个比较// 最终堆空了，比较全部结束while(h.size()) {let n = h.pop(); // 弹出堆顶元素，最小值p.next = n; // 将堆顶元素挂载在新链表上p = p.next; // 链表指针移位，为下次连接做准备n.next && h.insert(n.next) // 将弹出的堆顶元素的下一个元素入堆，进行重新构建堆结构}return res.next; // 返回的是next, 因为其第一个节点是我们new出来，用于连接的，所以不包含第一个节点
}

• 时间复杂度 O(nlogk)
  • forEach O(k), k是链表数量
  • while循环遍历了所有链表的所有节点 O(n)，n是所有链表节点之和
  • 并且堆操作是O(logk)， 两者结合：O(nlogk)
  • 整体：O(nlogk)
• 空间复杂度 O(k)
  • 就是堆的大小
• 堆能高效、快速找出最大值和最小值，时间复杂度O(1)，堆顶是最大值或最小值
• 找出第K个最大(小)元素
  • 构建一个容量为k的堆，让每个元素都插入这个堆
  • 保持容量始终为k, 最终堆顶就是最大元素或最小元素
• 这个解法不算精妙，但是是两个数据结构（堆和链表）融合解题的典型