Heap pop操作的时间复杂度

Question

一直以来，我一直假设一个Heap上的pop操作的时间复杂度是O(1)。

是O(1)还是O(log(n))？

Answer 1

Ok O(1) 仅用于检索堆的根。要删除这个根，所有堆实现都有 O(log(n)) 时间复杂度。例如 python heapq 模块实现了一个带有数组的堆，数组的第一个元素总是堆的根。所以在删除根的时候，有一个从根向下到堆底的替换过程，耗时O(log(n))，O(log(n))是总的替换次数。