gpt4 book ai didi

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

转载 作者:行者123 更新时间:2023-12-05 01:17:40 30 4
gpt4 key购买 nike

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

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

尽管它们都是 O(logn),但更容易看出 heappushpopheappop 然后 heappush.

关于python-3.x - heapq.heappushpop 如何比 python 中的 heappop 和 heappush 更高效,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/49228574/

30 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com