Heap

来自wrc's Wiki
Weirane讨论 | 贡献2021年7月3日 (六) 06:24的版本
跳到导航 跳到搜索

时间复杂度

  • push:最坏 O(log n),平均 O(1)
  • pop:O(log n)

找前 n 大的数

参考 Python 的实现:https://github.com/python/cpython/blob/3.9/Lib/heapq.py#L521

  • 先 push n 个元素到小根堆中(找前 n 小则用大跟堆)
  • 对剩下的元素,和堆顶比较,若更大则替换堆顶