選擇排序 每次在n個(gè)記錄中選擇一個(gè)最小的需要比較n-1次，但是這樣的操作并沒有把每一趟的比較結(jié)果保存下來理茎，在后一趟的比較中黑界，有許多的比較在前一趟就已經(jīng)做過了，但是由于前一趟排序時(shí)并未保存這些比較結(jié)果皂林，所以后一趟排序時(shí)又重復(fù)執(zhí)行了這些比較操作朗鸠，因而記錄的比較次數(shù)比較多
如果可以做到每次在選擇最小記錄時(shí)，并根據(jù)比較結(jié)果對(duì)其他記錄做出相應(yīng)的調(diào)整础倍，那樣排序的總體效率就會(huì)非常高了烛占，而堆排序就是對(duì)簡單選擇排序進(jìn)行的一種改進(jìn)，這種改進(jìn)的效率是非常明顯的
一.堆結(jié)構(gòu)
1.堆是具有下列性質(zhì)的完全二叉樹：
（1）每個(gè)結(jié)點(diǎn)的值都大于或等于其左右孩子結(jié)點(diǎn)的值，稱為大頂堆忆家；
（2）或者每個(gè)結(jié)點(diǎn)的值都小于或等于其左右孩子結(jié)點(diǎn)的值犹菇，稱為小頂堆；
從堆的定義可知：根節(jié)點(diǎn)一定是堆中所有結(jié)點(diǎn)中共的最大值或者最小值
2.按照層序遍歷的方式給結(jié)點(diǎn)進(jìn)行編號(hào)芽卿，那么非葉結(jié)點(diǎn)的編號(hào)滿足如下關(guān)系：
1<=i<=[n/2] [n/2]表示不超過n/2的最大整數(shù)
因?yàn)?strong>完全二叉樹的性質(zhì)：（這里的i指的是編號(hào)）
（1）如果2i>n揭芍，那么這個(gè)i對(duì)應(yīng)的節(jié)點(diǎn)是葉節(jié)點(diǎn)，且沒有左孩子卸例，反之称杨，我們知道不是葉節(jié)點(diǎn)的節(jié)點(diǎn)就滿足2i<=n，即得到了上面的表達(dá)式
（2）編號(hào)為i的節(jié)點(diǎn)的左右子節(jié)點(diǎn)編號(hào)分別是2i和2i+1
那么按照層序遍歷的方式筷转，將最大堆和最小堆存入數(shù)組姑原，那么一定滿足上面的關(guān)系
二.堆排序算法
1.基本思想
將待排序的序列構(gòu)造成一個(gè)大頂堆，此時(shí)旦装，整個(gè)序列的最大值就是堆頂?shù)母?jié)點(diǎn)页衙，將它移走，然后將剩余的n-1個(gè)序列重新構(gòu)造一個(gè)堆阴绢，這樣就會(huì)得到n個(gè)元素中的次大值店乐，如此反復(fù)執(zhí)行，便能得到一個(gè)有序序列了
那么實(shí)現(xiàn)這個(gè)思想要解決兩個(gè)問題：
（1）如何由一個(gè)無序序列構(gòu)建成一個(gè)堆
（2）在輸出堆頂元素后呻袭，如何調(diào)整剩余元素稱為一個(gè)新的堆
2.代碼實(shí)現(xiàn)思路：
(1)無序序列調(diào)整為大頂堆
調(diào)整為大頂堆主要是遍歷非葉子節(jié)點(diǎn)眨八，對(duì)每個(gè)非葉子節(jié)點(diǎn)都找到其和左右子樹中的最大值，然后調(diào)換順序左电，調(diào)整最大值到雙親節(jié)點(diǎn)廉侧，按照這個(gè)過程，可以將一個(gè)無序序列調(diào)整為完全二叉樹篓足。
復(fù)雜度分析：
非葉子節(jié)點(diǎn)的個(gè)數(shù)大約為所有節(jié)點(diǎn)個(gè)數(shù)的一半段誊，而每個(gè)非葉子節(jié)點(diǎn)的處理時(shí)間都是常量時(shí)間，因此時(shí)間復(fù)雜度為O(n)
(2)排序:
外循環(huán)：i=1,2,,,k:
第i次循環(huán)栈拖，將堆頂元素和倒數(shù)第i個(gè)元素交換连舍，然后對(duì)前面的n-i個(gè)元素調(diào)整為最大堆，這里的調(diào)整略和上面的不同(原理涩哟，可參照算法導(dǎo)論)索赏，每次循環(huán)是從根節(jié)點(diǎn)到最大編號(hào)的葉節(jié)點(diǎn)進(jìn)行遍歷，調(diào)整每個(gè)節(jié)點(diǎn)和其子節(jié)點(diǎn)的最大值到雙親節(jié)點(diǎn)贴彼，每一次循環(huán)過后潜腻，序列的最后i個(gè)元素都是有序的
復(fù)雜度分析：
每次外循環(huán)從根節(jié)點(diǎn)到最后一層的葉節(jié)點(diǎn)只需要經(jīng)過log(n-i)次內(nèi)循環(huán)，如果我們需要得到序列的全排序器仗，復(fù)雜度計(jì)算就是logn+log(n-1)+log(n-2)+...+log1=log(n!)融涣，根據(jù)時(shí)間復(fù)雜度計(jì)算原則：只保留最高次方的，去掉常數(shù)系數(shù)，調(diào)整n個(gè)無序元素為有序的時(shí)間復(fù)雜度為O(log(n^n))=O(nlogn)暴心；
如果是topk妓盲，那么我們只需要外循環(huán)k次，那么復(fù)雜度就是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. 堆排序的應(yīng)用
海量數(shù)據(jù)的topk，即得到海量數(shù)據(jù)的topk元素
（1）如果沒有內(nèi)存限制弹沽，可以采用內(nèi)排序檀夹，將數(shù)據(jù)全部加載進(jìn)來進(jìn)行排序，可以采用類冒泡排序的思想策橘，循環(huán)k次炸渡，每次將第k大的元素調(diào)整到上面，內(nèi)存循環(huán)用來比較大小和交換元素順序丽已，復(fù)雜度是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])
復(fù)雜度還是比較大蚌堵，我們可以采用堆排序的方法：
（2）如果在有內(nèi)存限制的情況下，即我們無法將數(shù)據(jù)全部加載進(jìn)來沛婴，只能采用外排序方法吼畏，這里我們?nèi)匀徊捎枚雅判颍呛蜕厦娴亩雅判蛩悸泛瓦^程都不一樣嘁灯，區(qū)別在于上面我們是將數(shù)據(jù)全部加載到內(nèi)存泻蚊，實(shí)現(xiàn)的全排序（k=len(sequence1)，但是這里因?yàn)樵诓幌膬?nèi)存的情況下：
先初始化一個(gè)k維的數(shù)組存放海量數(shù)據(jù)的前k個(gè)元素丑婿，然后將這個(gè)k個(gè)元素構(gòu)建成一個(gè)最小堆性雄；
循環(huán)以下過程：再從海量數(shù)據(jù)的第k+1個(gè)元素進(jìn)行遍歷，每次比較前面的最小堆的根節(jié)點(diǎn)與后面的每個(gè)元素的大小羹奉，如果根節(jié)點(diǎn)元素小于后面的元素秒旋，那么將前面的根節(jié)點(diǎn)元素替換為這個(gè)元素；再重新調(diào)整這個(gè)數(shù)組為一個(gè)最小堆诀拭，這樣每次都會(huì)扔掉更小的元素迁筛，加進(jìn)來更大的元素，直至遍歷完所有元素炫加，得到的數(shù)組就是我們的topk
時(shí)間復(fù)雜度分析：一開始構(gòu)建最小堆的復(fù)雜度是O(K)瑰煎，然后后面遍歷了n-K個(gè)元素，每次的復(fù)雜度是O(K)俗孝，因此總復(fù)雜度是O(k+(n-k)logk)=O(nlogK)
空間復(fù)雜度分析：這里比上面的堆排序增加了一個(gè)K維的數(shù)組作為緩存topk元素
總的算法效率分析：減少了內(nèi)存的消耗酒甸，空間復(fù)雜度和時(shí)間復(fù)雜度都比上面增加了
具體實(shí)現(xiàn)如下：
#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構(gòu)成的最小堆："+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不是內(nèi)部排序的，因?yàn)槲覀兩厦婷看沃皇菢?gòu)建了最小堆赋铝，如果我們想要得到有序的topk插勤，進(jìn)一步實(shí)現(xiàn)如下：
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)
即在內(nèi)存限制的情況下運(yùn)用堆排序?qū)崿F(xiàn)了海量數(shù)據(jù)的topk
