本文通过一道例题来介绍python中的最小堆


合并K个升序链表

import heapq
ListNode.__lt__ = lambda a, b: a.val < b.val  # 让堆可以比较节点大小
class Solution:    
    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:        
        cur = dummy = ListNode()  # 哨兵节点，作为合并后链表头节点的前一个节点        
        h = [head for head in lists if head]  # 初始把所有链表的头节点入堆        
        heapify(h)  # 堆化        
        while h:  # 循环直到堆为空                              
            node = heappop(h)  # 剩余节点中的最小节点            
            if node.next:  # 下一个节点不为空                
                heappush(h, node.next)  # 下一个节点有可能是最小节点，入堆            
            cur.next = node  # 合并到新链表中            
            cur = cur.next  # 准备合并下一个节点        
        return dummy.next  # 哨兵节点的下一个节点就是新链表的头节点

• __lt__特殊方法重载：

ListNode.__lt__ = lambda a, b: a.val < b.val   

__lt__ 是Python中的一个特殊方法，用于定义小于号 ( < ) 的行为。在这里，通过lambda表达式定义了 ListNode 类的小于号比较行为，使得 ListNode 对象可以比较大小，从而可以用于堆（优先队列）中。

• heapq 模块：

import heapq
heapify(h)  # 堆化   

heapq 是Python标准库中的堆队列算法模块。heapify 函数用于将列表 h 转换为堆（优先队列）。

• heappop 和 heappush 函数：

node = heappop(h)  # 剩余节点中的最小节点
if node.next:  # 下一个节点不为空    
    heappush(h, node.next)  # 下一个节点有可能是最小节点，入堆

heappop 函数用于从堆中弹出最小的元素， heappush 函数用于将元素插入堆中，并保持堆的性质。