算法子目錄：http://www.reibang.com/p/02492be3c5f5
題
現(xiàn)在有n個(gè)數(shù)蝉稳，設(shè)計(jì)算法找出前k大個(gè)數(shù)
解決思路
- 排序后切片
使用快排排序后切片嘱吗，復(fù)雜度為O(nlogn+k) - “LOW B” 三人組
因?yàn)檫@三種排序可以通過(guò)控制外部循環(huán)決定排序次數(shù)船惨，時(shí)間復(fù)雜度為O(kn)
相比之下债沮，這種方法比第一種要快。 - 堆排序
最后就是堆排序鹿鳖，我們的主角扁眯。
使用堆排序的解決思路
- 取前K個(gè)元素組成一個(gè)小根堆，堆頂就是目前第k大的數(shù)翅帜。
- 依次向前遍歷原列表姻檀，對(duì)于列表中的元素，如果小于堆頂涝滴，則忽略該元素绣版，如果大于堆頂，則將堆頂替換為該元素歼疮，并且對(duì)堆進(jìn)行一次調(diào)整杂抽。
- 遍歷列表所有元素后，倒序彈出堆頂韩脏。
例子：
有列表 [6,8,1,9,3,0,7,2,4,5]缩麸，取前5大的數(shù)。
這樣我們就要取出前五個(gè)數(shù)赡矢，構(gòu)建一個(gè)小根堆如下：
1
3 6
9 8
列表內(nèi)剩余元素：0,7,2,4,5
然后將剩余元素一個(gè)一個(gè)和堆頂比較匙睹，大于堆頂則替換愚屁，小于堆頂則忽略:
元素0:0<1 忽略
元素7:7>1 替換济竹，調(diào)整
3
7 6
9 8
元素2:2<3 忽略
元素4:4>3 替換痕檬，調(diào)整
4
7 6
9 8
元素5:5>4 替換，調(diào)整
5
7 6
9 8
最后依次彈出堆頂：[5,7,6,9,8]
復(fù)雜度為O(klogk+(n-k)logk)=O(nlogk)送浊。
代碼如下：
def sift(li,low,high):
#li表示樹(shù)梦谜，low表示high的父節(jié)點(diǎn)，high表示樹(shù)的最后一個(gè)節(jié)點(diǎn)
tmp = li[low]
i = low
j = 2 * i + 1 #初始j指向左子節(jié)點(diǎn)
# i 指向空位袭景，j指向子節(jié)點(diǎn)
while j <= high: #退出的第二種情況：j大于high唁桩，說(shuō)明空
if j + 1 <= high and li[j] < li [j+1]:#如果右子節(jié)點(diǎn)存在，且大于左子節(jié)點(diǎn)
j += 1 #則使用右子節(jié)點(diǎn)
if li[j] > tmp:
#這里比較 li[j] 與 li[j] 的父節(jié)點(diǎn) li[i] 的大小耸棒，如果 li[j] 大于 li[i] 荒澡，則交換。
li[i] = li[j]
# 同時(shí)与殃，讓i保存j的位置单山，j再保存相應(yīng)的左子節(jié)點(diǎn)。 接著到while進(jìn)行判斷 j還在不在堆的范圍中幅疼。
i = j
j = 2 * i + 1
else: #退出的第一種情況：j的位置比tmp小米奸，說(shuō)明兩個(gè)子節(jié)點(diǎn)都比tmp小。
break
li[i] = tmp #把拿出來(lái)的那個(gè)值放在空位上面爽篷。
def topk(li,k):
heap = li[0:k]
for i in range(k//2-1,-1,-1):
sift(heap,i,k-1)
for i in range(k,len(li)):
if li[i] > heap[0]:
heap[0] = li[i]
sift(heap,0,k-1)
for i in range(k-1,-1,-1):
heap[0],heap[i] = heap[i],heap[0]
sift(heap,0,i-1)
