Heap pop 操作的时间复杂度
Ayo*_*ari 3 heap time-complexity data-structures
长期以来，我一直假设 Heap 上的 pop 操作的时间复杂度是O(1).
是O(1)还是O(log(n))？
OkO(1)仅用于检索堆的根。要删除这个根，所有的堆实现都有O(log(n))时间复杂度。例如，python heapq 模块实现了一个带有数组的堆，并且数组的第一个元素始终是堆的根。所以在删除根时，有一个从根向下到堆底的替换过程，需要 O(log(n)) 时间，O(log(n)) 是替换的总次数。
- 您应该区分**堆**（*抽象数据结构*）和“二进制堆”（这是数据结构课程中经常教授的最简单的变体）。 (3认同)
- @meowgoesthedog “抽象数据结构”这个术语听起来很混乱；堆是一种“类型”的数据结构（通常理解为二叉堆，它是一种数据结构），它实现的抽象数据类型称为优先级队列。 (2认同)