python - 遍历堆化列表

Question

我正在进行蒙特卡洛模拟。作为这项任务的一部分，我生成了在一个区间内均匀分布的样本 (0,100) .

generate = lambda: uniform(0,100)

当所有最近的生成点对满足条件时，迭代停止。

check = lambda a,b: True if (b-a)<5 else False

我需要一些结构来有效地保留所有生成的点，并能够按升序遍历它们以执行 check在所有后续对上。

有一个 heapq Python 中的模块，它支持非常有效的堆结构。我决定使用它。

我遇到了一个问题。我没有发现这个模块支持的遍历过程。我发现按升序访问堆值的唯一方法是使用 heapq.heappop .但它会从堆中删除值。

我找到了解决方法，只是将堆对象复制到新堆对象中并使用 heappop 进行迭代在新的。但我认为每次迭代都将整个结构复制到内存中并不是很有效。

有没有其他方法可以让我更有效地完成我想做的事情？

---

用于说明的简化代码。

import heapq
from random import uniform
from itertools import tee, izip, count
from copy import copy


def pairwise(iterable): #get values from iterator in pairs
    a, b = tee(iterable)
    next(b, None)
    return izip(a, b)


check = lambda a,b: True if (b-a)<5 else False
generate = lambda: uniform(0,100)


def iterate_heap(heap):
    heap = copy(heap) #Here I have to copy the heap to be able to traverse
    try:
        while True:
            yield heapq.heappop(heap)
    except IndexError:
        return


def trial():
    items = []

    for i in count():
        item = generate()
        heapq.heappush(items, item)

        it = iterate_heap(items)
        it = pairwise(it)

        if i>0 and all(check(a,b) for a,b in it): #if i==0 then 'it' returns no values and 'all' returns True
            return i

print "The solution is reached. It took %d iterations." % trial()

paiwise功能来自 here 的配方.

---

更新:在此实现中使用 heappop每次迭代的复杂度是 O(n*log(n)) :

复制堆:O(n)

向堆中添加一个新值:O(log(n))

遍历:n元素 * O(log(n))从堆中弹出每个值 -> O(n*log(n)) .

结果:O(n+log(n)+n*log(n)) = O(n*log(n)

但我希望遍历为 O(n) ，因此最终的复杂度为 O(n) .

顺便说一句，如果我们只使用排序列表，我们需要在每次添加时对列表进行排序，所以 O(n*log(n)) , 但遍历将是 n*O(1) -> O(n) .因此，最终的复杂度仍然是 O(n*log(n)) .

我找到了解决办法。就是用bisect模块。找到要添加的地方是 O(log(n)) .添加到列表中的是 O(n) (由于实现，插入到位后的所有值都必须移动)。遍历为O(n) .因此，由此产生的复杂度为 O(n) .

不过，如果有一种方法可以在 Python 中使用堆来解决这个任务，我仍然很想知道。

Answer 1

我会在堆上使用 list.sort()。这使得堆条件完好无损，并且可以直接迭代底层列表。

FWIW，Timsort list.sort 使用的算法将利用堆中已存在的偏序。