小编jin*_*han的帖子

我有一个关于bisect和heapq的问题.

首先,我将向您展示2个版本的代码,然后询问有关它的问题.

使用bisect的版本:

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的版本

while len(scoville) > 1:
    a = heapq.heappop(scoville)
    #pops out smallest unit
    if a >= K:
        break
    b = heapq.heappop(scoville)
    #pops out smallest unit
    c = a + b * 2
    heapq.heappush(scoville, c)

两种算法都使用2个弹出和1个​​插入.

据我所知,在使用bisect的版本中,list的弹出操作是O(1),而bisect类的插入操作是O(logn).

在使用heapq的版本中,堆的弹出操作是O(1),堆的插入操作平均为O(logn).

因此,两个代码应该具有相同的时间效率.但是,使用bisect的版本是在某些代码挑战站点保持失败的时间效率测试.

有没有人有好的猜测？

*scoville是一个整数列表