Python heapq模块 -优先队列

heapq模块(Heap Queue)堆队列,或优先队列。堆实际是一个使用数组实现的完全二叉树,这个数据结构非常适合表示优先队列。如果你不熟悉堆,查看wiki上的解释。

heapq的主要属性是:每次pop出的元素都是最小值;不管怎么push/pop元素,都维持这个堆结构。

Python heapq模块中的函数

  • heapify(iterable):使用iterable对象构造堆
  • heappush(heap, ele):向堆中插入数据
  • heappop(heap):从堆中移除并获得最小的元素

  • heappushpop(heap, ele):等同于先执行push操作,再执行pop操作;为了提高效率
  • heapreplace(heap, ele):同上,不同的是,它先执行pop操作

  • nlargest(n, heap, key = fun):获得n个最大的元素
  • nsmallest(n, heap, key = fun):获得n个最小的元素

Linux内核使用的堆排序算法:

相关文章

发表评论

电子邮件地址不会被公开。 必填项已用*标注