选择排序 每次在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
