插入heapq比插入平分快吗？

Question

我有一个关于平分和heapq的问题。在

首先，我将向您展示两个版本的代码，然后询问有关它的问题。在

使用对分的版本：

while len(scoville) > 1:
    a = scoville.pop(0)
    #pops out smallest unit
    if a >= K:
        break
    b = scoville.pop(0)
    #pops out smallest unit
    c = a + b * 2
    bisect.insort(scoville, c)

使用heapq的版本

^{pr2}$

两种算法都使用2个pop和1个insert。在

我知道，在使用对分的版本中，list的pop操作是O（1），bisect类的插入操作是O（logn）。在

在使用heapq的版本中，堆的pop操作平均为O（1），堆的插入操作平均为O（logn）。在

所以这两个代码应该具有大致相同的时间效率。然而，使用bisect的版本是在一些代码挑战站点保持失败的时间效率测试。在

有人猜对了吗？在

*scoville是一个整数列表

Answer 1

你的假设是错误的。既不是pop(0)O（1），也不是{}O（logn）。在

问题是，在这两种情况下，弹出或插入的元素之后的所有元素都必须向左移动一个位置，或者可能，从而使两个操作都为O（n）。在

来自^{}文档：

bisect.insort_left(a, x, lo=0, hi=len(a))

Insert x in a in sorted order. This is equivalent to a.insert(bisect.bisect_left(a, x, lo, hi), x) assuming that a is already sorted. Keep in mind that the O(log n) search is dominated by the slow O(n) insertion step.

您可以通过创建一个非常长的列表来测试这一点，比如l = list(range(10**8))，然后执行l.pop(0)或{}和{}或{}。最后的弹出和插入操作应该是即时的，而其他操作有一个短暂但明显的延迟。 如果您交替地弹出和插入以使列表的长度在数千次运行中保持不变，您也可以使用%timeit在较短的列表上重复测试：

>>> l = list(range(10**6))
>>> %timeit l.pop(); bisect.insort(l, 10**6)
100000 loops, best of 3: 2.21 us per loop
>>> %timeit l.pop(0); bisect.insort(l, 0)
100 loops, best of 3: 14.2 ms per loop

因此，使用bisect的版本是O（n），带有heapq的版本是O（logn）。在