python-3.x - heapq.heappushpop 如何比 python 中的 heappop 和 heappush 更高效

Question

在 heapq 的文档中，它写道

heapq.heappushpop(heap, item)

Push item on the heap, then pop and return the smallest item from the heap. The combined action runs more efficiently than heappush() followed by a separate call to heappop().

为什么效率更高？
而且它的效率要高得多吗？

Answer 1

• heappop是先弹出第一个元素，然后移动最后一个元素填充到第一个位置，然后做下沉操作，通过连续交换将元素向下移动。从而恢复头部
  它是 O(logn)
  然后你headpush，把元素放在最后，然后冒泡像 heappop 但相反
  另一个O(logn)

• 在heappushpop时，弹出第一个元素，而不是将最后一个元素移到顶部，而是将新元素放在顶部，然后做一个下沉的 Action 。这与 heappop 的操作几乎相同。
  只有一个O(logn)

尽管它们都是 O(logn)，但更容易看出 heappushpop 比 heappop 然后 heappush.