底层设计:

  • 完全二叉树(除了最后一层,其他层都是满的,最后一层的节点都靠左排列)
  • 每个节点的值都小于等于左右子节点的值
  • 使用list存储

入堆heappush:

  • 先放入list尾部
  • 依次和上一层的父节点比较,如果比父节点小则交换(_siftdown上浮)

移除堆顶元素heappop:

  • 记录最后要返回的结果即heap[0]
  • 将heap[-1]弹出并赋值给heap[0],从堆顶依次和左右节点中的大节点交换(_siftup下沉)

有序堆heapify:

  • 从非叶子节点到根节点逆序依次下沉

返回一个无序列表前n个最小值nsmallest:

  • 等效于sorted(iterrable, key=key)[:n]
  • 用前n个元素构建一个大顶堆,后续元素与堆顶堆顶比较,如果小于堆顶则替换之并下沉