Как работает heapq.merge в python

Question

Как heapq.merge() сортировать список даже без генерации списка?

Не уверен, если я изложил ясно.
Таким образом, это связано с проблемой Super Ugly Number в 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]

Мне было трудно понять это. После того, как я искал понятия "yield" и "heapq", я все еще не понимаю этого в while петля, как merged знать, что ugly in uglies>n не будет меньше чем uglies[n-1],

Answer 1

Реализация heapq.merge это чистый Python, вы можете прочитать его код напрямую, если хотите.

Как вы можете догадаться из модуля, в котором он реализован, он использует кучу для объединения передаваемых итераций. Если итераторы (в данном случае - генераторы) выдают свои значения по порядку, они объединят их так, чтобы значения, которые они выдают, также были в порядке. Это не устраняет повторяющиеся значения, поэтому код, который вы показываете, проверяет, совпадает ли последнее значение с предыдущим.

Answer 2

Это занимает уже отсортированные итерации. Затем он может посмотреть на наименьшее значение в каждом из них и использовать его. Наименьшим всегда является первый элемент, затем второй элемент, затем третий элемент, поскольку каждый из них отсортирован.