引子：五分鐘玩轉(zhuǎn)面試考點(diǎn)-數(shù)據(jù)結(jié)構(gòu)系列套鹅，不會(huì)像那種嚴(yán)肅、古板的教科書般的博客文章揽祥，而是將晦澀難懂的概念和知識(shí)點(diǎn)盡可能幽默的細(xì)說出來，或結(jié)合生活場(chǎng)景檩电，或從零開始分析拄丰。帶給大家一個(gè)嚴(yán)肅而不失風(fēng)趣的數(shù)據(jù)結(jié)構(gòu)。
咳咳：俗話說：脫離業(yè)務(wù)的技術(shù)俐末，就是耍流氓料按。那么我就要提出這篇文章的靈魂一問了，請(qǐng)聽題：
1. 1千萬整數(shù)找出重復(fù)次數(shù)最多的100個(gè)整數(shù)卓箫。
2. 如何找出每日訪問網(wǎng)站最高的10個(gè)IP载矿。
3. 有一個(gè)1GB大小的文件，里面的每一行是一個(gè)詞烹卒，詞的大小不超過16個(gè)字節(jié)闷盔，內(nèi)存限制大小是1MB。返回頻數(shù)最高的100個(gè)詞旅急。
這個(gè)時(shí)候逢勾，感覺就是M個(gè)數(shù)中選擇N個(gè)數(shù) ，就是TOP N問題呀藐吮，是不是腦海中不由自主的蹦出了排序算法啦~
哈哈溺拱，咱就按照這個(gè)思路走。然后谣辞，表面不慌迫摔，假裝思索中ing，其實(shí)內(nèi)心再想：排序算法是啥呀泥从？
這里簡(jiǎn)單提下：
冒泡排序攒菠，核心思想：相鄰比較。每次將最大的浮出水面歉闰。
快速排序辖众，核心思想：分治法+挖坑填數(shù)。每次選擇一基數(shù)和敬，排序完成左邊比基數(shù)小凹炸，右邊比基數(shù)大。一直切分（分治）昼弟，直至選出無序的最大的N個(gè)整數(shù)啤它。
堆排序（出場(chǎng)自帶豬腳光環(huán)~），可以創(chuàng)建一個(gè)N大小的最小堆。然后balabala变骡。
這時(shí)候你可能要打斷一下了:啥离赫？最小堆？我這是要選出最大的N個(gè)元素呀塌碌？有木有搞錯(cuò)渊胸？emmm等等，啥叫堆台妆？翎猛？？啥叫最小堆接剩？切厘？？為什么不選最大堆呢懊缺？疫稿？？
請(qǐng)聽我戲說一下：
基礎(chǔ)概念：
堆：分為最大堆和最小堆鹃两，其實(shí)就是完全二叉樹而克，最大堆要求父節(jié)點(diǎn)的元素都大于等于子節(jié)點(diǎn)，最小堆要求父節(jié)點(diǎn)元素小于等于子節(jié)點(diǎn)怔毛。
下面圖解下如何生成大根堆：
我就拿（內(nèi)心PS：讀書人的事情，怎么能說偷呢腾降？）一下圖吧拣度，放在這里這里讓大家容易理解~~
給定一個(gè)列表array=[16,7,3,20,17,8]，對(duì)其進(jìn)行堆排序螃壤。
首先根據(jù)該數(shù)組元素構(gòu)建一個(gè)完全二叉樹抗果，得到
然后需要構(gòu)造初始堆，則從最后一個(gè)非葉節(jié)點(diǎn)開始調(diào)整奸晴，調(diào)整過程如下：
第一步：找到最后一個(gè)組（非葉節(jié)點(diǎn)）冤馏，左節(jié)點(diǎn)8 pk 擂主3，左孩子8勝利寄啼！然后3和8互相調(diào)換位置逮光。敗者3沒有子節(jié)點(diǎn)，結(jié)束比賽墩划。
從右到左涕刚。組內(nèi)pk，左子樹20 pk 右子樹17 左子樹20勝利乙帮，獲得挑戰(zhàn)擂主7的機(jī)會(huì)杜漠。左子樹20 pk 擂主7 左子樹20勝利，20和7交換位置。敗者7沒有子節(jié)點(diǎn)驾茴，結(jié)束比賽盼樟。
從下到上，左子樹20 PK 右子樹8锈至，左子樹20勝利晨缴。獲得挑戰(zhàn)擂主16的機(jī)會(huì)。左子樹20 pk 擂主16 左子樹勝利裹赴，交換位置喜庞。
此時(shí)敗者16含有孩子節(jié)點(diǎn)，將被挑戰(zhàn)棋返。
組內(nèi)挑戰(zhàn)開始：左子樹7和右子樹17組內(nèi)pk睛竣，右子樹17勝利晰房。獲取挑戰(zhàn)擂主16的機(jī)會(huì)。右子樹17和擂主16pk射沟，右子樹17勝利殊者，交換位置。敗者16無孩子節(jié)點(diǎn)验夯，結(jié)束比賽猖吴。
這樣就得到了初始堆。
哈哈挥转，相信到這里海蔽，基本懂得同學(xué)還是懂，不懂得還是一臉XX绑谣。這是哪党窜？我在干什么？你是誰借宵？
咱們慢慢分析：
無序數(shù)組轉(zhuǎn)化為大根堆步驟：
1.找到最后一個(gè)非葉節(jié)點(diǎn)幌衣，從右到左，從下到上壤玫，遍歷所有非葉節(jié)點(diǎn)豁护；
2.若是父節(jié)點(diǎn)小于最大的子節(jié)點(diǎn)，那么交換父子節(jié)點(diǎn)的位置欲间，但是要注意择镇，交換之后對(duì)其他節(jié)點(diǎn)的影響。
我們的目標(biāo)是：
(沒有蛀牙....)根節(jié)點(diǎn)一定是樹中最大的值括改。同時(shí)腻豌，父節(jié)點(diǎn)大于子節(jié)點(diǎn)家坎。
切回到我們的問題。此時(shí)吝梅，你應(yīng)該基本知道了堆的概念虱疏，為什么不選最大堆呢？因?yàn)樵蹅冞x最小堆就是采用末位淘汰制苏携。將堆中最小元素剔除做瞪。
每次最小堆調(diào)整后，總會(huì)將整個(gè)堆中最小的元素放在根節(jié)點(diǎn)上右冻，然后我們分別取出[N-1,M]中的元素装蓬，若大于堆頂，則替換纱扭。然后（隨著堆的蠕動(dòng)牍帚，你可以動(dòng)態(tài)想想這個(gè)畫面~~）再次將最小元素選出放于堆頂。直至堆里保存的都是最大的元素乳蛾。
此時(shí)暗赶，你會(huì)想怎么細(xì)節(jié)怎么實(shí)現(xiàn)的：如何確定最后一個(gè)非葉節(jié)點(diǎn)呢？如何精確找到每一個(gè)孩子節(jié)點(diǎn)呢肃叶？
嘿嘿蹂随，我可真是一個(gè)小機(jī)靈鬼...，放心因惭，全都給你整的明明白白的~
如何確定父節(jié)點(diǎn)和子節(jié)點(diǎn)的下標(biāo)位置呢岳锁？
(1) 它的左孩子結(jié)點(diǎn)是：R[2i+1];
(2) 它的右孩子結(jié)點(diǎn)是：R[2i+2];
(3) 它的父結(jié)點(diǎn)是：R[(i-1)/2];
騙誰呢？具體解釋下蹦魔，不要粘貼公式糊弄你的小可愛們激率！哼~
那好，咱們從零分析一下：
還是上面的數(shù)組版姑，證據(jù)在上面，咱們就開始分析啦：
array=[16,7,3,20,17,8] 一個(gè)長度為6的數(shù)組迟郎。
咱們從i=5剥险，最后一個(gè)元素array[5]開始說起：
父節(jié)點(diǎn)：(i-1)/2=2，他的父節(jié)點(diǎn)就是i=2宪肖，array[2]也就是3表制。
子節(jié)點(diǎn)：2i+1=11，等等兄得控乾，你越界了...你根本沒有孩子節(jié)點(diǎn)...(名偵探小胖)
于是我就大膽推測(cè)一下么介，最后一個(gè)非子節(jié)點(diǎn)就是array[2]。
反向推理一下：i=2時(shí)蜕衡，左孩子：2i+1=5壤短，右孩子：2i+2=6，但是最大下標(biāo)是5，那么只有一個(gè)孩子節(jié)點(diǎn)array[5]也就是8久脯。
那倒數(shù)第二個(gè)下標(biāo)非葉節(jié)點(diǎn)的下標(biāo)是啥纳胧？
博主內(nèi)心獨(dú)白：emmm我也不知道....繼續(xù)套公式，看看有啥規(guī)律不帘撰。
數(shù)組倒數(shù)第二個(gè)下標(biāo)數(shù)是i=4跑慕，(i-1)/2=1，那么下標(biāo)array[1]就是第2個(gè)父節(jié)點(diǎn)摧找。
數(shù)組倒數(shù)第三個(gè)下標(biāo)數(shù)是i=3核行，(i-1)/2=1，也是下標(biāo)array[1]蹬耘。
那倒數(shù)第一個(gè)下標(biāo)非葉節(jié)點(diǎn)的下標(biāo)是啥芝雪？
數(shù)組倒數(shù)第四個(gè)下標(biāo)數(shù)是i=2，(i-1)/2=1婆赠，那么下標(biāo)array[0]就是第3個(gè)父節(jié)點(diǎn)绵脯。
數(shù)組倒數(shù)第三個(gè)下標(biāo)數(shù)是i=1，(i-1)/2=1休里，也是下標(biāo)array[0]蛆挫。
此時(shí)還有嗎？
數(shù)組倒數(shù)第五個(gè)下標(biāo)數(shù)是i=0妙黍，(i-1)/2=-1悴侵，也是下標(biāo)array[-1]。
也就是根節(jié)點(diǎn)沒有父節(jié)點(diǎn)了....
等等拭嫁，我好像發(fā)現(xiàn)啥規(guī)律了...
父節(jié)點(diǎn)是array[2]=3 array[1]=7 array[0]=16可免。
array=[16,7,3,20,17,8]
在我找到最后一個(gè)非葉節(jié)點(diǎn) i 之后，通過i-1找到其他非葉節(jié)點(diǎn)做粤，直到根節(jié)點(diǎn)的下標(biāo)是0浇借。
可是，概念太多怕品，記不住呀妇垢。沒事，安排好了肉康，結(jié)合一個(gè)生活場(chǎng)景闯估，真正做到熟記于心~
結(jié)合生活場(chǎng)景解釋一下：
現(xiàn)在要開始 XX聯(lián)盟S17 的比賽，比賽組根據(jù)玩家投票新采用了一種新的比賽規(guī)則吼和，規(guī)則如下：
橫向：每個(gè)新晉擂主可以參與更高一級(jí)的比賽涨薪，直至選出冠軍。登頂大根堆頂峰炫乓；
縱向：每個(gè)下臺(tái)擂主要被更低一級(jí)的選手挑戰(zhàn)刚夺，需要證明自己實(shí)力献丑，也可能被一擼到底；
簡(jiǎn)言之：能者上光督，弱者下
每一小組選出最強(qiáng)者阳距，參與擂主pk，勝利者獲取下一次挑戰(zhàn)機(jī)會(huì)结借；失敗者要被挑戰(zhàn)纷妆，直至完成一場(chǎng)勝利糕再，或者排名倒數(shù)。
//比賽開始-請(qǐng)各小組按順序進(jìn)行比賽（從排名最后一個(gè)小組開始）
public static int[] createMaxHeap(int[] arr) {
int length = arr.length;
//冠軍下標(biāo)是0
for (int i = (length - 1-1) / 2; i >= 0; i--) {
//開啟小組擂臺(tái)賽
doJustHeapMove(arr, i, length);
}
return arr;
}
而后，開始了激烈的小組比賽馒铃，擂主先把收拾自己的東西悦施，因?yàn)樗膊恢雷约菏且粩⊥康剡€是保持原位鼎姐！心里有些忐忑~
//小組擂臺(tái)開始
private static void doJustHeapMove(int[] arr, int root, int length) {
int temp = arr[root]; //擂主將自己的東西保存好
//確定小組成員掸掏，確保每一個(gè)人都有機(jī)會(huì)挑戰(zhàn)（最后元素:length-1）
//若發(fā)起挑戰(zhàn)，擂主失敗薪韩，那么就會(huì)子節(jié)點(diǎn)挑戰(zhàn)
//每次開始确沸，均獲取到小組成員編號(hào)（而開始的root若是挑戰(zhàn)失敗，便成為了lChild）
for (int lChild = 2 * root + 1; lChild < length; lChild = 2 * lChild + 1) {
//判斷左節(jié)點(diǎn)是否是length-2俘陷，即不是最后一個(gè)元素罗捎！
//若是最后一個(gè)元素，小組只有自己拉盾，直接參與擂臺(tái)賽
//選出小組最強(qiáng)者桨菜，準(zhǔn)備參與擂主pk，
if (lChild < length - 1 && arr[lChild + 1] > arr[lChild]) {
lChild++;
}
//擂臺(tái)賽開始
if (temp >= arr[lChild]) {
break; //小組擂臺(tái)賽結(jié)束捉偏，開始下一小組的比賽
} else {
arr[root] = arr[lChild]; //成員升級(jí)（擂主）
root = lChild; //擂主降級(jí)（獲取到降級(jí)的編號(hào)）
}
}
//擂主降級(jí)賽結(jié)束倒得，灰溜溜的走了~
arr[root] = temp;
}
我還會(huì)回來的(擂主內(nèi)心獨(dú)白)~~
力扣解法
兜兜轉(zhuǎn)轉(zhuǎn)，從第一篇博客到2021.08.22已經(jīng)過去了2年半多了夭禽。今天又回到這個(gè)題目霞掺。帶來一種最小堆更加簡(jiǎn)潔的實(shí)現(xiàn)。即依賴JDK API來實(shí)現(xiàn)最小堆讹躯，只需要使得最小堆維護(hù)top n個(gè)元素即可菩彬。
class Solution {
/**
* 最小堆實(shí)現(xiàn)TOP N
*/
public int findKthLargest(int[] nums, int k) {
//定義的最小堆
PriorityQueue<Integer> queue = new PriorityQueue<>(k, (a, b) -> a - b);
//最小堆，先入k個(gè)元素
for (int i = 0; i < k; i++) {
queue.add(nums[i]);
}
for (int i = k; i < nums.length; i++) {
//取出堆頂元素蜀撑，但不移除
int min = queue.peek();
//若num[i]大于堆中最小元素挤巡，即堆中最小元素不是Top N
if (nums[i] > min) {
//移除堆頂元素
queue.poll();
//將元素放入堆中
queue.offer(nums[i]);
}
}
return queue.peek();
}
}
