最小堆

例题:

力扣第23题:合并k个升序链表

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

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

示例 1:

1
2
3
4
5
6
7
8
9
10
输入: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:

1
2
输入:lists = []
输出:[]

示例 3:

1
2
输入:lists = [[]]
输出:[]

23. 合并 K 个升序链表 - 力扣(LeetCode)

最小堆

定义:
1、堆是一颗完全二叉树;

2、堆中的某个结点的值总是大于等于(最大堆)或小于等于(最小堆)其孩子结点的值。

3、堆中每个结点的子树都是堆树。

imgimg

python heapq库

最小堆的编写用到heapq库,堆的使用一般用于排序

heapq — 堆队列算法 — Python 3.12.2 文档

小知识

res.append(path)相当于append进去path的引用,如果你此时改path,那么res里面的结果也会变,这两是指向同一个对象的。path[:]相当于重新赋值了一个对象


最小堆
http://example.com/2024/03/19/最小堆-title/
作者
SuperNiuNiu
发布于
2024年3月19日
许可协议