选择排序 每次在n个记录中选择一个最小的需要比较n-1次，但是这样的操作并没有把每一趟的比较结果保存下来，在后一趟的比较中，有许多的比较在前一趟就已经做过了，但是由于前一趟排序时并未保存这些比较结果，所以后一趟排序时又重复执行了这些比较操作，因而记录的比较次数比较多
如果可以做到每次在选择最小记录时，并根据比较结果对其他记录做出相应的调整，那样排序的总体效率就会非常高了，而堆排序就是对简单选择排序进行的一种改进，这种改进的效率是非常明显的

一.堆结构
1.堆是具有下列性质的完全二叉树：
（1）每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆；
（2）或者每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆；
从堆的定义可知：根节点一定是堆中所有结点中共的最大值或者最小值

2.按照层序遍历的方式给结点进行编号，那么非叶结点的编号满足如下关系：
1<=i<=[n/2] [n/2]表示不超过n/2的最大整数
因为完全二叉树的性质：（这里的i指的是编号）
（1）如果2i>n，那么这个i对应的节点是叶节点，且没有左孩子，反之，我们知道不是叶节点的节点就满足2i<=n，即得到了上面的表达式
（2）编号为i的节点的左右子节点编号分别是2i和2i+1
那么按照层序遍历的方式，将最大堆和最小堆存入数组，那么一定满足上面的关系

二.堆排序算法
1.基本思想
将待排序的序列构造成一个大顶堆，此时，整个序列的最大值就是堆顶的根节点，将它移走，然后将剩余的n-1个序列重新构造一个堆，这样就会得到n个元素中的次大值，如此反复执行，便能得到一个有序序列了
那么实现这个思想要解决两个问题：
（1）如何由一个无序序列构建成一个堆
（2）在输出堆顶元素后，如何调整剩余元素称为一个新的堆

2.代码实现思路：
(1)无序序列调整为大顶堆
调整为大顶堆主要是遍历非叶子节点，对每个非叶子节点都找到其和左右子树中的最大值，然后调换顺序，调整最大值到双亲节点，按照这个过程，可以将一个无序序列调整为完全二叉树。
复杂度分析：
非叶子节点的个数大约为所有节点个数的一半，而每个非叶子节点的处理时间都是常量时间，因此时间复杂度为O(n)

(2)排序:
外循环：i=1,2,,,k:
第i次循环，将堆顶元素和倒数第i个元素交换，然后对前面的n-i个元素调整为最大堆，这里的调整略和上面的不同(原理，可参照算法导论)，每次循环是从根节点到最大编号的叶节点进行遍历，调整每个节点和其子节点的最大值到双亲节点，每一次循环过后，序列的最后i个元素都是有序的
复杂度分析：
每次外循环从根节点到最后一层的叶节点只需要经过log(n-i)次内循环，如果我们需要得到序列的全排序，复杂度计算就是logn+log(n-1)+log(n-2)+...+log1=log(n!)，根据时间复杂度计算原则：只保留最高次方的，去掉常数系数，调整n个无序元素为有序的时间复杂度为O(log(n^n))=O(nlogn)；
如果是topk，那么我们只需要外循环k次，那么复杂度就是logn+log(n-1)+log(n-2)+...log(n-k)=O(log(n^k))=klogn

"""
heap-sort
"""
def heap_sort(lst,k):
    """
    contrust a max-heap based on given array ranging from the last non-leaf node to root node
    in python:non-leaf node number reduce from half of the last index of the array minus 1 to 0
    """
    for i in range((len(lst)-1-1)/2,-1,-1):
        heap_adjust(lst,i,len(lst)-1)
    print "\n"
    """
    put the the top of the heap in the end of array in turn,then re-construct a max-heap
    finally we can get a array whose element is sorted from small to large，if we only get
    the top k ,then we iterate k times ,in other words,we need put the top of the heap in
    the end k times
    """
    for j in range(len(lst)-1, len(lst)-1-k, -1):
        """
        swap the top of the heap and the last of unordered part ,if we iterate
        k times ,then we get a array whose the last k elements is the top k
        """
        # print lst[0]
        lst[j], lst[0]=lst[0], lst[j]
        heap_adjust(lst, 0, j-1)

def heap_adjust(lst,s,m):
    """
    re-contruct a max-heap from s to m based on array
    """
    i = 2*s+1 #the left node of the s
    temp=lst[s]
    while i <= m:
        if (i < m) and (lst[i] < lst[i+1]):
            i = i+1
        if temp >= lst[i]:
            break
        else:
            lst[s] = lst[i]
        s = i
        i=i*2+1
        # print lst
    lst[s]=temp

if __name__=="__main__":
    sequence1=[50,10,90,30,70,40,80,60,20]
    k=5
    heap_sort(sequence1,k)
    topk=sequence1[-k:len(sequence1)]
    topk.reverse()
    print "topk:"+str(topk)

运行结果

2. 堆排序的应用
海量数据的topk，即得到海量数据的topk元素
（1）如果没有内存限制，可以采用内排序，将数据全部加载进来进行排序，可以采用类冒泡排序的思想，循环k次，每次将第k大的元素调整到上面，内存循环用来比较大小和交换元素顺序，复杂度是n-1+n-2+...+n-k)=O(kn)

#coding=UTF-8
"""
inner sort
"""
sequence = [-23,18,2,3,9,-4,5,7]
k = 5
for i in range(k):
    for j in range(i + 1, len(sequence)):
        if sequence[i] < sequence[j]:
            sequence[i], sequence[j] = sequence[j], sequence[i]
    print sequence
print "topk:"+str(sequence[:k - 1])

运行结果

复杂度还是比较大，我们可以采用堆排序的方法：

（2）如果在有内存限制的情况下，即我们无法将数据全部加载进来，只能采用外排序方法，这里我们仍然采用堆排序，但是和上面的堆排序思路和过程都不一样，区别在于上面我们是将数据全部加载到内存，实现的全排序（k=len(sequence1)，但是这里因为在不消耗内存的情况下：
先初始化一个k维的数组存放海量数据的前k个元素，然后将这个k个元素构建成一个最小堆；
循环以下过程：再从海量数据的第k+1个元素进行遍历，每次比较前面的最小堆的根节点与后面的每个元素的大小，如果根节点元素小于后面的元素，那么将前面的根节点元素替换为这个元素；再重新调整这个数组为一个最小堆，这样每次都会扔掉更小的元素，加进来更大的元素，直至遍历完所有元素，得到的数组就是我们的topk
时间复杂度分析：一开始构建最小堆的复杂度是O(K)，然后后面遍历了n-K个元素，每次的复杂度是O(K)，因此总复杂度是O(k+(n-k)logk)=O(nlogK)
空间复杂度分析：这里比上面的堆排序增加了一个K维的数组作为缓存topk元素
总的算法效率分析：减少了内存的消耗，空间复杂度和时间复杂度都比上面增加了
具体实现如下：

#coding=UTF-8
"""
heap-sort
"""
def heap_adjust(lst,s,m):
    i = 2*s+1 #the left node of the s
    temp=lst[s]
    while i <= m:
        if (i < m) and (lst[i] > lst[i+1]):
            i = i+1
        if temp <= lst[i]:
            break
        else:
            lst[s] = lst[i]
        s = i
        i=i*2+1
        # print lst
    lst[s]=temp

def heap_sort(lst,k):
    topk = []
    m=0
    while len(topk) < k:
        topk.append(lst[m])
        m+=1
    print "初始tok:"+str(topk)
    for i in range((k-1-1)/2,-1,-1):
        heap_adjust(topk,i,k-1)
    min_k=topk[0]
    print "初始最小值:"+str(min_k)
    print "初始topk构成的最小堆："+str(topk)
    print "\n"
    for j in range(k,len(lst)):
        # print lst[0]
        if min_k<lst[j]:
            topk[0]=lst[j]
            for i in range((k-1-1)/2, -1, -1):
                heap_adjust(topk,i,k-1)
            min_k=topk[0]
        # print topk
    return topk

if __name__=="__main__":
    sequence1=[50,10,90,30,70,40,80,60,20]
    k=5
    print "最后得到的topk:"+str(heap_sort(sequence1,k))

运行结果

可以看出来：这里得到的topk不是内部排序的，因为我们上面每次只是构建了最小堆，如果我们想要得到有序的topk，进一步实现如下：

if __name__=="__main__":
    sequence1=[50,10,90,30,70,40,80,60,20]
    k=5
    topk=heap_sort(sequence1,k)
    print "小顶堆tok:"+str(topk)
    for j in range(len(topk)-1,-1,-1):
        topk[0],topk[j]=topk[j],topk[0]
        heap_adjust(topk,0,j-1)
    print "有序的topk："+str(topk)

运行结果

即在内存限制的情况下运用堆排序实现了海量数据的topk