heapq.heappushpop 比 python 中的 heappop 和 heappush 更高效
How is heapq.heappushpop more efficient than heappop and heappush in python
在 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().
为什么效率更高？
它的效率也高得多吗？
heappop就是pop出第一个元素，然后移动最后一个元素填充到第一个位置，然后做下沉操作，通过连续交换将元素向下移动.从而恢复头部
这是 O(logn)
然后你headpush，把元素放在最后，然后bubble-up
喜欢 heappop 但相反
另一个 O(logn)
而heappushpop，弹出第一个元素，而不是将最后一个元素移到顶部，而是将新元素放在顶部，然后进行下沉动作。这几乎与 heappop.
相同的操作
只有一个 O(logn)
如上，即使它们都是 O(logn)，但更容易看出 heappushpop 比 heappop 快，然后是 heappush。
heappushpop 压入一个元素，然后弹出最小的元素。如果您推送的元素小于堆的最小值，则无需执行任何操作。因为我们知道我们尝试推送的元素（小于堆最小值）将在以下情况下弹出我们分两次操作。
这很有效，不是吗？
在 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().
为什么效率更高？
它的效率也高得多吗？
heappop就是pop出第一个元素，然后移动最后一个元素填充到第一个位置，然后做下沉操作，通过连续交换将元素向下移动.从而恢复头部
这是O(logn)
然后你headpush，把元素放在最后，然后bubble-up 喜欢heappop但相反
另一个O(logn)而
heappushpop，弹出第一个元素，而不是将最后一个元素移到顶部，而是将新元素放在顶部，然后进行下沉动作。这几乎与heappop.
相同的操作 只有一个O(logn)
如上，即使它们都是 O(logn)，但更容易看出 heappushpop 比 heappop 快，然后是 heappush。
heappushpop 压入一个元素，然后弹出最小的元素。如果您推送的元素小于堆的最小值，则无需执行任何操作。因为我们知道我们尝试推送的元素（小于堆最小值）将在以下情况下弹出我们分两次操作。
这很有效，不是吗？