Top K問題應(yīng)該是當(dāng)前互聯(lián)網(wǎng)中非常普遍的應(yīng)用場景了，如搜索引擎的熱門關(guān)鍵字排序纺非，電商網(wǎng)站的熱銷商品排序等抹剩。由于互聯(lián)網(wǎng)數(shù)據(jù)非常龐大，因此通常來說結(jié)果集的規(guī)模遠(yuǎn)小于原始數(shù)據(jù)集的規(guī)模绪励。
Top K問題最直接的解法是：對(duì)整個(gè)數(shù)據(jù)集進(jìn)行排序肿孵，然后取出頭K個(gè)數(shù)據(jù)作為結(jié)果集（也是解題時(shí)想到的解法）唠粥。因?yàn)閷?duì)整個(gè)數(shù)據(jù)集進(jìn)行了排序，所以算法的最優(yōu)時(shí)間復(fù)雜度為O(n * logn)停做。
顯然晤愧，由于只需要取出Top K個(gè)數(shù)據(jù)，剩余數(shù)據(jù)集的排序結(jié)果可以忽略蛉腌，所以有了第二種算法：循環(huán)k次并在每次循環(huán)中找出結(jié)果集中的最大數(shù)字官份。這種算法的時(shí)間復(fù)雜度為O(k * n)，考慮到結(jié)果數(shù)據(jù)集的數(shù)量遠(yuǎn)小于原始數(shù)據(jù)集的大小烙丛，因此相對(duì)來說是一種更快的算法舅巷。
但在第二種算法中，每次循環(huán)中都需要重新對(duì)數(shù)據(jù)集進(jìn)行全量遍歷從才能獲得最大值河咽，浪費(fèi)了一部分時(shí)間钠右。通過翻閱資料，發(fā)現(xiàn)堆排序可以很好的彌補(bǔ)算法二中的弱點(diǎn)：當(dāng)堆構(gòu)造出來之后忘蟹，它能夠通過樹的層級(jí)來保存一部分?jǐn)?shù)據(jù)的排序信息飒房，因此在每次獲取最大（小）值的過程中媚值，只需要獲取堆的第一個(gè)元素（樹的根節(jié)點(diǎn)）狠毯，將第一個(gè)節(jié)點(diǎn)和最后一個(gè)節(jié)點(diǎn)交換（保證堆的完全二叉樹性質(zhì)），最后做局部的調(diào)整保證堆的層級(jí)排序信息褥芒。而對(duì)于Top K問題嚼松，整個(gè)過程包括了初始化堆和之后的取值-交換-調(diào)整堆，算法的時(shí)間復(fù)雜度降到了O(n + k * logn)也就是O(k * logn)锰扶。
最后献酗，在本地電腦上針對(duì)從包含5000000個(gè)整數(shù)的數(shù)據(jù)集中取出20個(gè)最大的整數(shù)的場景進(jìn)行了測試，三種算法分別花費(fèi)的時(shí)間為：算法一（快速排序）：570ms少辣；算法二（線性查找）：170ms凌摄；算法三（對(duì)查找）：16ms。
