底层设计:
- 完全二叉树(除了最后一层,其他层都是满的,最后一层的节点都靠左排列)
- 每个节点的值都小于等于左右子节点的值
- 使用list存储
入堆heappush:
- 先放入list尾部
- 依次和上一层的父节点比较,如果比父节点小则交换(_siftdown上浮)
移除堆顶元素heappop:
- 记录最后要返回的结果即heap[0]
- 将heap[-1]弹出并赋值给heap[0],从堆顶依次和左右节点中的大节点交换(_siftup下沉)
有序堆heapify:
- 从非叶子节点到根节点逆序依次下沉
返回一个无序列表前n个最小值nsmallest:
- 等效于sorted(iterrable, key=key)[:n]
- 用前n个元素构建一个大顶堆,后续元素与堆顶堆顶比较,如果小于堆顶则替换之并下沉