Python heapq 源码阅读
Heap 作为一种重要的数据结构,有许多应用场景,比如优先级队列,每次出队的都是最大值或者最小值的元素。很多语言都集成了相关实现,比如 Java 的 PriorityQueue,而 Python 提供了 heapq 模块。 因为 Heap 通常用数组而不是链表存储,所以 Python 里面的 Heap 实质上就是一个列表,而 heapq 提供的几个函数也是以列表对象作为参数的: from heapq import heappush, heappop, heappify, heapreplace, heappushpop heap = [] heappush(heap, 1) item = heap[0] # 第一个元素代表堆顶元素 heappop(heap) heapify([3, 2, 1, 5, 6, 4]) # 把普通列表转化为堆结构 [1, 2, 3, 4, 5, 6] heapreplace([3, 4, 5], 1) # 直接将堆顶元素 3 替换为 1,最后堆结构为 [1, 4, 5] heappushpop([3, 4, 5], 1) # 先将 1 插入堆中,再 pop 出堆顶元素,最后堆结构为 [3, 4, 5] 为什么 heapq 提供的是最小堆而不是更常见的最大堆呢?这就得从源码中找答案了。...