如何在heapq中用最小的键有效地弹出所有元素？

Question

我正在做一个模拟实验，并试图使我的代码尽可能有效。在一部分中，我使用heapq模块实现了一个最小堆优先级队列。你知道吗

在整个模拟过程中，我必须用最小的键弹出所有元素。要做到这一点，最简单的方法是：

    elements = []
    k1, v1 = heapq.heappop(heap)
    elements.append((k1,v1))
    k2, v2 = heap[0] #looks at the smallest item without popping
    while(k1 == k2):
         k1, v1 = heapq.heappop(heap)
         elements.append((k1,v1))
         k2, v2 = heap[0]
    return elements

Answer 1

你展示的一般技巧既简单又有效。但你在做一些不必要的额外任务。下面是一个小优化。你知道吗

elements = []
k1, v1 = heapq.heappop(heap)
elements.append((k1,v1))
while(k1 == heap[0]):
     k2, v2 = heapq.heappop(heap)
     elements.append((k2,v2))
return elements

为了安全起见，您可能应该添加检查以确保堆不是空的。当堆中没有项时检查heap[0]是件坏事，如果堆为空则调用heapq.heappop也是件坏事。你知道吗

Answer 2

我打算建议将结构从(k, v)堆更改为k堆和{k:[v]}字典。这将使您的代码变成：

k = heap[0]
return [(k,v) for v in hash[k]]

使用：

hash = defaultdict(list)
heap = []

heappush(heap, (k, v))会变成：

heappush(heap, k)
hash[k].append(v)

heappop(heap)将变成：

k = heappop(heap)
v = hash[k].pop()