分类 Python 下的文章

Python 的 heapq 模块源码分析


起步

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

20190107115023.jpg

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

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


Python 的枚举类型


起步

Python 的原生类型中并不包含枚举类型。为了提供更好的解决方案,Python 通过 PEP 435 在 3.4 版本中添加了 enum 标准库。

枚举类型可以看作是一种标签或是一系列常量的集合,通常用于表示某些特定的有限集合,例如星期、月份、状态等。在没有专门提供枚举类型的时候我们是怎么做呢,一般就通过字典或类来实现:

Color = {
    'RED'  : 1,
    'GREEN': 2,
    'BLUE' : 3,
}

class Color:
    RED   = 1
    GREEN = 2
    BLUE  = 3

这种来实现枚举如果小心翼翼地使用当然没什么问题,毕竟是一种妥协的解决方案。它的隐患在于可以被修改。