堆是一个近似完全二叉树的结构,并同时满足如下性质

子节点的键值或索引总是小于(或者大于)它的父节点

python标准库模块heapq实现了堆排序的一些算法,主要提供了以下几个函数

  1. heapify(x):本地把列表转换为堆,时间复杂度O(n)
  2. heappush(heap, item):将新项添加到堆,并保持堆的不变性
  3. heappop(heap):从堆中取出最小项,并保持堆的不变性
  4. heapreplace(heap, item):从堆中取出最小项,并将新项添加到堆,并保持堆的不变性
  5. heappushpop(heap, item):从堆中取出最小项,并将新项添加到堆,并保持堆的不变性(速度更快)
  6. nsmallest(n, iterable, key=None):从可迭代对象中返回前n个最小项
  7. nlargest(n, iterable, key=None):从可迭代对象中返回前n个最大项
  8. merge(*iterables, key=None, reverse=False):合并多个可排序对象
最后修改日期: 2021-10-09