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

Question

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

不知道我说清楚了没有。
所以，这是从leetcode的 Super Ugly Number 问题提出的。

还有这个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]

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

Answer 1

它需要 n 个已经排序的可迭代对象。然后它可以查看每个值中的最小值并使用它。最小的始终是第一项，然后是第二项，然后是第三项，因为它们都是已排序的。