Python中的heapq模块源码详析

起步

这是一个相当实用的内置模块，但是很多人竟然不知道他的存在——笔者也是今天偶然看到的，哎……尽管如此，还是改变不了这个模块好用的事实

heapq 模块实现了适用于Python列表的最小堆排序算法。

堆是一个树状的数据结构，其中的子节点都与父母排序顺序关系。因为堆排序中的树是满二叉树，因此可以用列表来表示树的结构，使得元素 N 的子元素位于 2N + 1 和 2N + 2 的位置（对于从零开始的索引）。

本文内容将分为三个部分，第一个部分简单介绍 heapq 模块的使用；第二部分回顾堆排序算法；第三部分分析heapq中的实现。

heapq 的使用

创建堆有两个基本的方法：heappush() 和 heapify()，取出堆顶元素用 heappop()。

heappush() 是用来向已有的堆中添加元素，一般从空列表开始构建：

import heapqdata = [97, 38, 27, 50, 76, 65, 49, 13]heap = []for n in data: heapq.heappush(heap, n)print('pop:', heapq.heappop(heap)) # pop: 13print(heap) # [27, 50, 38, 97, 76, 65, 49]

如果数据已经在列表中，则使用 heapify() 进行重排：

import heapqdata = [97, 38, 27, 50, 76, 65, 49, 13]heapq.heapify(data)print('pop:', heapq.heappop(data)) # pop: 13print(data) # [27, 38, 49, 50, 76, 65, 97]

回顾堆排序算法

堆排序算法基本思想是：将无序序列建成一个堆，得到关键字最小（或最大的记录；输出堆顶的最小 （大）值后，使剩余的 n-1 个元素 重又建成一个堆，则可得到n个元素的次小值 ；重复执行，得到一个有序序列，这个就是堆排序的过程。

堆排序需要解决两个问题：

先来看看第二个问题的解决方法。采用的方法叫“筛选”，当输出堆顶元素之后，就将堆中最后一个元素代替之；然后将根结点值与左、右子树的根结点值进行比较 ，并与其中小者进行交换；重复上述操作，直至叶子结点，将得到新的堆，称这个从堆顶至叶子的调整过程为“筛选”。