data-structures - Heap pop 操作的时间复杂度

Question

很长一段时间，我一直假设Heap上的pop操作的时间复杂度是O(1) .

是吗O(1)或 O(log(n)) ?

Answer 1

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