Python heapq：拆分并合并成一个有序的heapq

Question

我想拆分两个 heapq（用作优先级队列），然后将它们相加并使生成的 heapq 相对于之前的两个 heapq 排序。

这在 python 中可行吗？

我当前的代码：

population = []
for i in range(0, 6):
    heappush(population, i)
new_population = []
for i in range(4, 9):
    heappush(new_population, i)

split_index = len(population) // 2
temp_population = population[:split_index]
population = new_population[:split_index] + temp_population
print(population)
print(heappop(population))

输出：

[4, 5, 6, 0, 1, 2]
4

想要的输出：

[0, 1, 2, 4, 5, 6]
0

Answer 1

使用nlargest代替切片，然后重新堆化组合列表。

from heapq import nlargest, heapify
n = len(population) // 2
population = heapify(nlargest(population, n) +
                     nlargest(new_population, n))
print(heappop(population))

您可能想要进行基准测试，但是，如果对两个原始列表进行排序，然后合并结果，速度会更快。 Python 的 sort 例程对于几乎已排序的列表来说速度很快，并且这可能比 heapq 函数施加的开销少得多。如果您实际上不需要优先级队列（因为您无论如何都要对它们进行排序），那么最后 heapify 步骤可能不是必需的。

from itertools import islice
from heapq import merge, heapify
n = len(population)  # == len(new_population), presumably
population = heapify(islice(merge(sorted(population), sorted(new_population)), n))

Python heapq：拆分并合并成一个有序的heapq

Python heapq: Split and merge into a ordered heapq

python

heap

priority-queue