思路一：時間復(fù)雜度為O(N*logk)
對前k個數(shù)撑瞧，建立最大堆，對于后面N-k個數(shù)显蝌，依次和最大堆的最大數(shù)比較预伺，如果小于最大數(shù)，則替換最大數(shù)曼尊，并重新建立最大堆酬诀。
堆排序：
我們舉例，假若從10000萬個數(shù)里選出前100個最大的數(shù)據(jù)骆撇。
首先我們先分析：既然要選出前100個最大的數(shù)據(jù)瞒御，我們就建立一個大小為100的堆（建堆時就按找最大堆的規(guī)則建立，即每一個根節(jié)點(diǎn)都大于它的子女節(jié)點(diǎn)）神郊，然后再將后面的剩余數(shù)據(jù)若符合要求就插入堆中肴裙，不符合就直接丟棄該數(shù)據(jù)。
那我們現(xiàn)在考慮：確定是該選擇最大堆的數(shù)據(jù)結(jié)構(gòu)還是最小堆的數(shù)據(jù)結(jié)構(gòu)呢涌乳。
分析一下：
若選用最大堆的話蜻懦，堆頂是堆的最大值，我們考慮既然要選出從10000萬個數(shù)里選出前100個最大的數(shù)據(jù)爷怀，我們在建堆的時候阻肩，已經(jīng)考慮了最大堆的特性，那這樣的話最大的數(shù)據(jù)必然在它頂端运授。假若真不巧，我開始的前100個數(shù)據(jù)中已經(jīng)有這10000個數(shù)據(jù)中的最大值了乔煞，那對于我后面剩余的10000-100的元素再想入堆是不是入不進(jìn)去了Ｓ蹼！渡贾！所以逗宜，選用最大堆從10000萬個數(shù)里選出前100個最大的數(shù)據(jù)只能找出一個，而不是100個空骚。
那如果選用最小堆的數(shù)據(jù)結(jié)構(gòu)來解決纺讲，最頂端是最小值，再次遇到比它大的值囤屹，就可以入堆熬甚，入堆后重新調(diào)整堆，將小的值pass掉肋坚。這樣我們就可以選出最大的前K個數(shù)據(jù)了乡括。言外之意肃廓，假若我們要找出N個數(shù)據(jù)中最小的前k個數(shù)據(jù)，就要用最大堆了诲泌。
那如果選用最小堆的數(shù)據(jù)結(jié)構(gòu)來解決盲赊，最頂端是最小值，再次遇到比它大的值敷扫，就可以入堆哀蘑，入堆后重新調(diào)整堆，將小的值pass掉葵第。這樣我們就可以選出最大的前K個數(shù)據(jù)了绘迁。
時間復(fù)雜度：n*logk
一個堆的元素數(shù)目為K時，堆的高度至多為logk羹幸。建立堆的時間為klogk脊髓。而調(diào)整的次數(shù)為n-k，每次調(diào)整的時間為logk栅受，所以調(diào)整的時間為 (n-k)logk将硝，所以總的時間復(fù)雜度為nlogk。
nlogk = klogk + (n-k)logk
假若我們要找出N個數(shù)據(jù)中最大的前k個數(shù)據(jù)屏镊，就要用最小頂堆了依疼。
假若我們要找出N個數(shù)據(jù)中最小的前k個數(shù)據(jù)，就要用最大頂堆了而芥。
思路二：時間復(fù)雜度為O(k*n)
先排序前k個數(shù)律罢，對于后面N-k個數(shù)，依次進(jìn)行插入棍丐。
當(dāng)k很小時误辑，可以用這種算法
思路三：復(fù)雜度O(N*logN).
先直接排序，再取排序后數(shù)據(jù)的前k個數(shù)歌逢。
排序算法用最快的堆排序巾钉，復(fù)雜度也會達(dá)到O(N*logN).
當(dāng)k接近于N時，可以用這種算法秘案。
引自：https://blog.csdn.net/hanjing_1995/article/details/51539593
引自：http://www.cnblogs.com/studynote/
