Python中的heapq模块源码详析

起步

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

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

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

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

heapq 的使用

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

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

import heapq

data = [97, 38, 27, 50, 76, 65, 49, 13]
heap = []

for n in data:
 heapq.heappush(heap, n)

print('pop:', heapq.heappop(heap)) # pop: 13
print(heap) # [27, 50, 38, 97, 76, 65, 49]

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

import heapq

data = [97, 38, 27, 50, 76, 65, 49, 13]

heapq.heapify(data)

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

回顾堆排序算法

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

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

  • 如何由一个无序序列建立成一个堆?
  • 如何在输出堆顶元素之后,调整剩余元素,使之成为一个新的堆?
  • 新添加元素和,如何调整堆?

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

如上图所示,当堆顶 13 输出后,将堆中末尾的 97 替代为堆顶,然后堆顶与它的子节点 38 和 27 中的小者交换;元素 97 在新的位置上在和它的子节点 65 和 49 中的小者交换;直到元素97成为叶节点,就得到了新的堆。这个过程也叫 下沉 。

让堆中位置为 pos 元素进行下沉的如下:

def heapdown(heap, pos):
 endpos = len(heap)
 while pos < endpos:
 lchild = 2 * pos + 1
 rchild = 2 * pos + 2
 if lchild >= endpos: # 如果pos已经是叶节点,退出循环
  break
 childpos = lchild # 假设要交换的节点是左节点
 if rchild < endpos and heap[childpos] > heap[rchild]:
  childpos = rchild

 if heap[pos] < heap[childpos]: # 如果节点比子节点都小,退出循环
  break
 heap[pos], heap[childpos] = heap[childpos], heap[pos] # 交换
 pos = childpos

再来看看如何解决第三个问题:新添加元素和,如何调整堆?这个的方法正好与 下沉 相反,首先将新元素放置列表的最后,然后新元素与其父节点比较,若比父节点小,与父节点交换;重复过程直到比父节点大或到根节点。这个过程使得元素从底部不断上升,从下至上恢复堆的顺序,称为 上浮 。

将位置为 pos 进行上浮的代码为:

def heapup(heap, startpos, pos): # 如果是新增元素,startpos 传入 0
 while pos > startpos:
 parentpos = (pos - 1) // 2
 if heap[pos] < heap[parentpos]:
  heap[pos], heap[parentpos] = heap[parentpos], heap[pos]
  pos = parentpos
 else:
  break

第一个问题:如何由一个无序序列建立成一个堆?从无序序列的第 n/2 个元素 (即此无序序列对应的完全二叉树的最后一个非终端结点 )起 ,至第一个元素止,依次进行下沉:

for i in reversed(range(len(data) // 2)):
 heapdown(data, i)

heapq 源码分析

添加新元素到堆中的 heappush() 函数:

def heappush(heap, item):
 """Push item onto heap, maintaining the heap invariant."""
 heap.append(item)
 _siftdown(heap, 0, len(heap)-1)

把目标元素放置列表最后,然后进行上浮。尽管它命名叫 down ,但这个过程是上浮的过程,这个命名也让我困惑,后来我才知道它是因为元素的索引不断减小,所以命名 down 。下沉的过程它也就命名为 up 了。

def _siftdown(heap, startpos, pos):
 newitem = heap[pos]
 # Follow the path to the root, moving parents down until finding a place
 # newitem fits.
 while pos > startpos:
  parentpos = (pos - 1) >> 1
  parent = heap[parentpos]
  if newitem < parent:
   heap[pos] = parent
   pos = parentpos
   continue
  break
 heap[pos] = newitem

一样是通过 newitem 不断与父节点比较。不一样的是这里缺少了元素交换的过程,而是计算出新元素最后所在的位置 pos 并进行的赋值。显然这是优化后的代码,减少了不断交换元素的冗余过程。

再来看看输出堆顶元素的函数 heappop():

def heappop(heap):
 """Pop the smallest item off the heap, maintaining the heap invariant."""
 lastelt = heap.pop() # raises appropriate IndexError if heap is empty
 if heap:
  returnitem = heap[0]
  heap[0] = lastelt
  _siftup(heap, 0)
  return returnitem
 return lastelt

通过 heap.pop() 获得列表中的最后一个元素,然后替换为堆顶 heap[0] = lastelt ,再进行下沉:

def _siftup(heap, pos):
 endpos = len(heap)
 startpos = pos
 newitem = heap[pos]
 # Bubble up the smaller child until hitting a leaf.
 childpos = 2*pos + 1 # 左节点,默认替换左节点
 while childpos < endpos:
  # Set childpos to index of smaller child.
  rightpos = childpos + 1 # 右节点
  if rightpos < endpos and not heap[childpos] < heap[rightpos]:
   childpos = rightpos # 当右节点比较小时,应交换的是右节点
  # Move the smaller child up.
  heap[pos] = heap[childpos]
  pos = childpos
  childpos = 2*pos + 1
 # The leaf at pos is empty now. Put newitem there, and bubble it up
 # to its final resting place (by sifting its parents down).
 heap[pos] = newitem
 _siftdown(heap, startpos, pos)

这边的代码将准备要下沉的元素视为新元素 newitem ,将其当前的位置 pos 视为空位置,由其子节点中的小者进行取代,反复如此,最后会在叶节点留出一个位置,这个位置放入 newitem ,再让新元素进行上浮。

再来看看让无序数列重排成堆的 heapify() 函数:

def heapify(x):
 """Transform list into a heap, in-place, in O(len(x)) time."""
 n = len(x)
 for i in reversed(range(n//2)):
  _siftup(x, i)

这部分就和理论上的一致,从最后一个非叶节点 (n // 2) 到根节点为止,进行下沉。

总结

堆排序结合图来理解还是比较好理解的。这种数据结构常用于优先队列(标准库Queue的优先队列用的就是堆)。 heapq 模块中还有很多其他 heapreplace ,heappushpop 等大体上都很类似。

好了,以上就是这篇文章的全部内容了,希望本文的内容对大家的学习或者工作具有一定的参考学习价值,如果有疑问大家可以留言交流,谢谢大家对我们的支持。

(0)

相关推荐

  • 详解Python中heapq模块的用法

    heapq 模块提供了堆算法.heapq是一种子节点和父节点排序的树形数据结构.这个模块提供heap[k] <= heap[2*k+1] and heap[k] <= heap[2*k+2].为了比较不存在的元素被人为是无限大的.heap最小的元素总是[0]. 打印 heapq 类型 import math import random from cStringIO import StringIO def show_tree(tree, total_width=36, fill=' '): ou

  • Python cookbook(数据结构与算法)实现优先级队列的方法示例

    本文实例讲述了Python实现优先级队列的方法.分享给大家供大家参考,具体如下: 问题:要实现一个队列,它能够以给定的优先级对元素排序,且每次pop操作时都会返回优先级最高的那个元素: 解决方案:采用heapq模块实现一个简单的优先级队列 # example.py # # Example of a priority queue import heapq class PriorityQueue: def __init__(self): self._queue = [] self._index =

  • Python实现优先级队列结构的方法详解

    最简单的实现 一个队列至少满足2个方法,put和get. 借助最小堆来实现. 这里按"值越大优先级越高"的顺序. #coding=utf-8 from heapq import heappush, heappop class PriorityQueue: def __init__(self): self._queue = [] def put(self, item, priority): heappush(self._queue, (-priority, item)) def get(

  • Python heapq使用详解及实例代码

     Python heapq 详解 Python有一个内置的模块,heapq标准的封装了最小堆的算法实现.下面看两个不错的应用. 小顶堆(求TopK大) 话说需求是这样的: 定长的序列,求出TopK大的数据. import heapq import random class TopkHeap(object): def __init__(self, k): self.k = k self.data = [] def Push(self, elem): if len(self.data) < self

  • Python利用heapq实现一个优先级队列的方法

    实现一个优先级队列,每次pop的元素要是优先级高的元素,由于heapq.heapify(list)默认构建一个小顶堆,因此要将priority变为相反数再push,代码如下: import heapq class PriorityQueue(object): """实现一个优先级队列,每次pop优先级最高的元素""" def __init__(self): self._queue = [] self._index = 0 def push(sel

  • Python中的heapq模块源码详析

    起步 这是一个相当实用的内置模块,但是很多人竟然不知道他的存在--笔者也是今天偶然看到的,哎--尽管如此,还是改变不了这个模块好用的事实 heapq 模块实现了适用于Python列表的最小堆排序算法. 堆是一个树状的数据结构,其中的子节点都与父母排序顺序关系.因为堆排序中的树是满二叉树,因此可以用列表来表示树的结构,使得元素 N 的子元素位于 2N + 1 和 2N + 2 的位置(对于从零开始的索引). 本文内容将分为三个部分,第一个部分简单介绍 heapq 模块的使用:第二部分回顾堆排序算法

  • Python中的 enum 模块源码详析

    起步 上一篇 <Python 的枚举类型> 文末说有机会的话可以看看它的源码.那就来读一读,看看枚举的几个重要的特性是如何实现的. 要想阅读这部分,需要对元类编程有所了解. 成员名不允许重复 这部分我的第一个想法是去控制 __dict__ 中的 key .但这样的方式并不好,__dict__ 范围大,它包含该类的所有属性和方法.而不单单是枚举的命名空间.我在源码中发现 enum 使用另一个方法.通过 __prepare__ 魔术方法可以返回一个类字典实例,在该实例 使用 __prepare__

  • YOLOv5中SPP/SPPF结构源码详析(内含注释分析)

    目录 一.SPP的应用的背景 二.SPP结构分析 三.SPPF结构分析 四.YOLOv5中SPP/SPPF结构源码解析(内含注释分析) 总结 一.SPP的应用的背景 在卷积神经网络中我们经常看到固定输入的设计,但是如果我们输入的不能是固定尺寸的该怎么办呢? 通常来说,我们有以下几种方法: (1)对输入进行resize操作,让他们统统变成你设计的层的输入规格那样.但是这样过于暴力直接,可能会丢失很多信息或者多出很多不该有的信息(图片变形等),影响最终的结果. (2)替换网络中的全连接层,对最后的卷

  • python如何使用contextvars模块源码分析

    目录 前记 更新说明 1.有无上下文传变量的区别 2.如何使用contextvars模块 3.如何优雅的使用contextvars 4.contextvars的原理 4.1 ContextMeta,ContextVarMeta和TokenMeta 4.2 Token 4.3 全局唯一context 4.4contextvar自己封装的Context 4.5 ContextVar 5.contextvars asyncio 5.1在asyncio中获取context 5.2 对上下文的操作 5.2

  • Java8中AbstractExecutorService与FutureTask源码详解

    目录 前言 一.AbstractExecutorService 1.定义 2.submit 3.invokeAll 4.invokeAny 二.FutureTask 1.定义 2.构造方法 3.get 4.run/ runAndReset 5. cancel 三.ExecutorCompletionService 1.定义 2.submit 3.take/ poll 总结 前言 本篇博客重点讲解ThreadPoolExecutor的三个基础设施类AbstractExecutorService.F

  • Python 中的 Counter 模块及使用详解(搞定重复计数)

    文章目录 参考描述Counter 模块Counter() 类Counter() 对象字典有序性KeyError魔术方法 \_\_missing\_\_ update() 方法 Counter 对象的常用方法most_common()elements()total()subtract() Counter 对象间的运算加法运算减法运算并集运算交集运算单目运算 Counter 对象间的比较>== 参考 项目 描述 Python 标准库 DougHellmann 著 / 刘炽 等 译 搜索引擎 Bing

  • 关于Redis网络模型的源码详析

    前言 Redis的网络模型是基于I/O多路复用程序来实现的.源码中包含四种多路复用函数库epoll.select.evport.kqueue.在程序编译时会根据系统自动选择这四种库其中之一.下面以epoll为例,来分析Redis的I/O模块的源码. epoll系统调用方法 Redis网络事件处理模块的代码都是围绕epoll那三个系统方法来写的.先把这三个方法弄清楚,后面就不难了. epfd = epoll_create(1024); 创建epoll实例 参数:表示该 epoll 实例最多可监听的

  • SPRING BOOT启动命令参数及源码详析

    前言 使用过Spring Boot,我们都知道通过java -jar可以快速启动Spring Boot项目.同时,也可以通过在执行jar -jar时传递参数来进行配置.本文带大家系统的了解一下Spring Boot命令行参数相关的功能及相关源码分析. 命令行参数使用 启动Spring Boot项目时,我们可以通过如下方式传递参数: java -jar xxx.jar --server.port=8081 默认情况下Spring Boot使用8080端口,通过上述参数将其修改为8081端口,而且通

  • Java1.8中StringJoiner的使用及源码详析

    前言 StringJoiner是Java里1.8新增的类,主要是帮助我们把一个列表拼接字符串, 或许有一部分人没有接触过. 所以本文将从使用例子入手, 分析StringJoiner的源码. 基本好的同学, 其实只要把这段例子自己运行一下, 自己看看源码就可以了.因为我觉得这个类挺简单的. 没必要看我下面的废话.... public class StringJoinerTest { public static void main(String[] args) { StringJoiner join

  • SpringBoot拦截器以及源码详析

    目录 1.拦截器是什么 2.自定义拦截器 2.1 编写拦截器 2.2 注册和配置拦截器 3.拦截器原理 3.1 找到可以处理请求的handler以及handler的所有拦截器 3.2 执行拦截器的preHandle方法 3.3 执行目标方法 3.4 执行拦截器的postHandle方法 3.5 执行拦截器的afterCompletion方法 3.6 异常处理 4.总结 1.拦截器是什么 java里的拦截器(Interceptor)是动态拦截Action调用的对象,它提供了一种机制可以使开发者在一

随机推荐