Python中的堆实现:heapq 模块——利用堆结构实现快速访问数据流中的中位数

堆结构 堆结构是一种优先队列,可以以任意顺序添加对象,并随时查找或删除最小(大)的元素,或者查找和删除前 K 个最小(大)元素。相比于列表方法min() / max(),这样做的效率要高得多。 堆结构是一种特殊的完全二叉树(除了叶子节点层外,其余层节点数均达到最大值,而叶子节点层所有节点都集中在左侧)。根节点的值不大于(小于)其子节点的值,并且子节点也服从这种特性。根节点值不大于子节点的堆称为小根堆,根节点的值不小于子节点的堆称为大根堆。如图左为小根堆,图右为大根堆。 Python中 heapq 模块 Python 中给出了小根堆的辅助实现库函数 heapq 模块(其中q表示队列,方便记忆)