最快找到一堆数里的最小值–最小堆。

Python heapq

python heapq 是 binary heap 的变种，见 binary heap
How to customize the heap order?
Have each element on the heap to be a tuple, with the first tuple element being one that accepts normal Python comparisons.

Eg.

>>> def heapsort(iterable):
...     h = []
...     for value in iterable:
...         heappush(h, value)
...     return [heappop(h) for i in range(len(h))]
...
>>> heapsort([1, 3, 5, 7, 9, 2, 4, 6, 8, 0])
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

基本用法

This module provides an implementation of the heap queue algorithm, also known as the priority queue algorithm.
Heaps are binary trees for which every parent node has a value less than or equal to any of its children. This implementation uses arrays for which heap[k] <= heap[2*k+1] and heap[k] <= heap[2*k+2] for all k, counting elements from zero. For the sake of comparison, non-existing elements are considered to be infinite. The interesting property of a heap is that its smallest element is always the root, heap[0].
The API below differs from textbook heap algorithms in two aspects: (a) We use zero-based indexing. This makes the relationship between the index for a node and the indexes for its children slightly less obvious, but is more suitable since Python uses zero-based indexing. (b) Our pop method returns the smallest item, not the largest (called a “min heap” in textbooks; a “max heap” is more common in texts because of its suitability for in-place sorting).
These two make it possible to view the heap as a regular Python list without surprises: heap[0] is the smallest item, and heap.sort() maintains the heap invariant!
To create a heap, use a list initialized to [], or you can transform a populated list into a heap via function heapify().
The following functions are provided:
heapq.heappush(heap, item)
Push the value item onto the heap, maintaining the heap invariant.
heapq.heappop(heap)
Pop and return the smallest item from the heap, maintaining the heap invariant. If the heap is empty, IndexError is raised. To access the smallest item without popping it, use heap[0].
heapq.heappushpop(heap, item)
Push item on the heap, then pop and return the smallest item from the heap. The combined action runs more efficiently than heappush() followed by a separate call to heappop().
New in version 2.6.
heapq.heapify(x)
Transform list x into a heap, in-place, in linear time.
heapq.heapreplace(heap, item)
Pop and return the smallest item from the heap, and also push the new item. The heap size doesn’t change. If the heap is empty, IndexError is raised.
This one step operation is more efficient than a heappop() followed by heappush() and can be more appropriate when using a fixed-size heap. The pop/push combination always returns an element from the heap and replaces it with item.
The value returned may be larger than the item added. If that isn’t desired, consider using heappushpop() instead. Its push/pop combination returns the smaller of the two values, leaving the larger value on the heap.
The module also offers three general purpose functions based on heaps.
heapq.merge(*iterables)
Merge multiple sorted inputs into a single sorted output (for example, merge timestamped entries from multiple log files). Returns an iterator over the sorted values.
Similar to sorted(itertools.chain(*iterables)) but returns an iterable, does not pull the data into memory all at once, and assumes that each of the input streams is already sorted (smallest to largest).
heapq.nlargest(n, iterable[, key])
Return a list with the n largest elements from the dataset defined by iterable. key, if provided, specifies a function of one argument that is used to extract a comparison key from each element in the iterable: key=str.lower Equivalent to: sorted(iterable, key=key, reverse=True)[:n]
heapq.nsmallest(n, iterable[, key])
Return a list with the n smallest elements from the dataset defined by iterable. key, if provided, specifies a function of one argument that is used to extract a comparison key from each element in the iterable: key=str.lower Equivalent to: sorted(iterable, key=key)[:n]

Time complexity
heapq.heapify(x): O(k)
heapq.heappush(heap, item): O(logk)
heapq.heappop(heap): O(logk)

对于 nsmallest 和 nlargest 的时间复杂度有点疑惑，找了些资料，就源代码而言，应该是 O(nlogt)，然而有一种说法是 O(t+n)，见 How does heapq.nlargest work?
source code，2.7 和 3.4 这一部分是一样的。

def nsmallest(n, iterable):
    """Find the n smallest elements in a dataset.
    Equivalent to:  sorted(iterable)[:n]
    """
    if n < 0:
        return []
    it = iter(iterable)
    result = list(islice(it, n))
    if not result:
        return result
    _heapify_max(result)
    _heappushpop = _heappushpop_max
    for elem in it:
        _heappushpop(result, elem)
    result.sort()
    return result

例题

23. Merge k Sorted Lists

Problem

Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.

Solution

'''
Solution:
    Find out the minimum value in a bunch of elements, we use minheap.
    Time complexity for heap: heapify: O(k)   push/poll an elem: O(logk)
    Space complexity: O(k)
    Time complexity: O(k+avg(n)klogk)
'''
# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution(object):
    def mergeKLists(self, lists):
        """
        :type lists: List[ListNode]
        :rtype: ListNode
        """
        root=ListNode(0)
        dummy=root
        h=[]
        for node in lists:
            if node:
                heapq.heappush(h,(node.val,node))
        while h:
            val,node=heapq.heappop(h)
            dummy.next=ListNode(val)
            dummy=dummy.next
            if node.next:
                heapq.heappush(h,(node.next.val,node.next))
        return root.next
'''
class Solution(object):
    def mergeKLists(self, lists):
        """
        :type lists: List[ListNode]
        :rtype: ListNode
        """
        largeList=[]
        for root in lists:
            while root:
                largeList.append(root.val)
                root=root.next
        largeList.sort()
        print largeList
        root=ListNode(0)
        dummy=root
        for n in largeList:
            print dummy.val
            dummy.next=ListNode(n)
            dummy=dummy.next
        return root.next
        '''