python heapq merge的内部工作。它如何在不生成列表的情况下对列表进行排序

Question

即使不生成列表，heapq.merge()如何对列表进行排序

不知道我说的是否清楚。
所以，这是从 Super Ugly Number problem at leetcode

这是python代码

class Solution(object):
    def nthSuperUglyNumber(self, n, primes):
        """
        :type n: int
        :type primes: List[int]
        :rtype: int
        """
        uglies = [1]
        def gen(prime):
            for ugly in uglies:
                yield ugly * prime
        merged = heapq.merge(*map(gen, primes))
        while len(uglies) < n:
            ugly = next(merged)
            if ugly != uglies[-1]:
                uglies.append(ugly)
        return uglies[-1]

这让我很难理解。在我搜索了“收益率”和“heapq”的概念之后，我仍然没有在while循环中得到它，如何merged知道ugly in uglies>n不会小于uglies[n-1]

Answer 1

它需要n已排序的项。然后，它可以查看其中每一个中的最小值并使用该值。最小的一个总是第一个项目，然后是第二个项目，然后是第三个项目，因为它们都已排序

Answer 2

heapq.merge的实现是纯Python的，如果需要，可以直接read its code

正如您可能从实现它的模块中猜到的，它使用一个堆来合并它所传递的iterables。如果iterables（本例中的生成器）按顺序生成它们的值，它将组合它们，以便生成的值也按顺序生成。它不会消除重复的值，这就是为什么您显示的代码会检查最新的值是否等于前一个值