小顶堆解决思路： 小顶堆维护当前扫描到的最大K个数，其后每一次的扫描到的元素， 若大于堆顶，则入堆，然后删除堆顶； 依此往复，直至扫描完所有元素

max-min

def partition(seq):

    pi, seq = seq[0], seq[1:]                
    lo = [x for x in seq if x <= pi]
    hi = [x for x in seq if x > pi]
    return lo, pi, hi

def selectmax(seq, k):
    lo, pi, hi = partition(seq)
    m = len(lo)
    if m == k: return pi
    if m < k: return select(hi, k-m-1)
    return select(lo, k)

def selectmin(seq, k):
    lo, pi, hi = partition(seq)
    m = len(lo)
    if m == k: return lo
    if m < k:
        lo.append(pi)
        return lo+select(hi, k-m-1)
    return select(lo, k)

max-min-heap

import heapq
import random
 
class TopkHeap(object):
    def __init__(self, k):
        self.k = k
        self.data = []
 
    def Push(self, elem):
        if len(self.data) < self.k:
            heapq.heappush(self.data, elem)
        else:
            topk_small = self.data[0]
            if elem > topk_small:
                heapq.heapreplace(self.data, elem)
 
    def TopK(self):
        return [x for x in reversed([heapq.heappop(self.data) for x in xrange(len(self.data))])]
        
class BtmkHeap(object):
    def __init__(self, k):
        self.k = k
        self.data = []

    def Push(self, elem):
        # Reverse elem to convert to max-heap
        elem = -elem
        # Using heap algorighem
        if len(self.data) < self.k:
            heapq.heappush(self.data, elem)
        else:
            topk_small = self.data[0]
            if elem > topk_small:
                heapq.heapreplace(self.data, elem)

    def BtmK(self):
        return sorted([-x for x in self.data])

min-heap

import heapq

def topK(lists, k):
    minp = []
    for i in lists:
        if len(minp) < k:
            minp.append(i)
        else:
            minp = heapq.nsmallest(k, minp)
            if minp[0] >= i:
                continue
            else:
                minp[0] = i
    return heapq.nlargest(k, minp)

quick-select

def q_k(A,k):
    if len(A)<k:
        return A
    
    pivot = A[-1]
    
    left = [pivot] + [i for i in A[:-1] if i>=pivot]
    
    leftlen = len(left)
    
    if leftlen==k:
        return left
        
    if leftlen > k:
        return q_k(left, k)
    
    else:
        right = [i for i in A[:-1] if i<pivot]
        
        return q_k(right, k-leftlen) + left