heapq.py 文件源码

def nsmallest(n, iterable):
    """Find the n smallest elements in a dataset.

    Equivalent to:  sorted(iterable)[:n]
    """
    if n < 0:
        return []
    if hasattr(iterable, '__len__') and n * 10 <= len(iterable):
        # For smaller values of n, the bisect method is faster than a minheap.
        # It is also memory efficient, consuming only n elements of space.
        it = iter(iterable)
        result = sorted(islice(it, 0, n))
        if not result:
            return result
        insort = bisect.insort
        pop = result.pop
        los = result[-1]    # los --> Largest of the nsmallest
        for elem in it:
            if elem < los:
                insort(result, elem)
                pop()
                los = result[-1]
        return result
    # An alternative approach manifests the whole iterable in memory but
    # saves comparisons by heapifying all at once.  Also, saves time
    # over bisect.insort() which has O(n) data movement time for every
    # insertion.  Finding the n smallest of an m length iterable requires
    #    O(m) + O(n log m) comparisons.
    h = list(iterable)
    heapify(h)
    return list(map(heappop, repeat(h, min(n, len(h)))))

# 'heap' is a heap at all indices >= startpos, except possibly for pos.  pos
# is the index of a leaf with a possibly out-of-order value.  Restore the
# heap invariant.