引子：五分鐘玩轉(zhuǎn)面試考點-數(shù)據(jù)結(jié)構(gòu)系列，不會像那種嚴肅、古板的教科書般的博客文章，而是將晦澀難懂的概念和知識點盡可能幽默的細說出來，或結(jié)合生活場景，或從零開始分析。帶給大家一個嚴肅而不失風(fēng)趣的數(shù)據(jù)結(jié)構(gòu)。

咳咳：俗話說：脫離業(yè)務(wù)的技術(shù)，就是耍流氓。那么我就要提出這篇文章的靈魂一問了，請聽題：

1. 1千萬整數(shù)找出重復(fù)次數(shù)最多的100個整數(shù)。
2. 如何找出每日訪問網(wǎng)站最高的10個IP。
3. 有一個1GB大小的文件，里面的每一行是一個詞，詞的大小不超過16個字節(jié)，內(nèi)存限制大小是1MB。返回頻數(shù)最高的100個詞。

這個時候，感覺就是M個數(shù)中選擇N個數(shù) ，就是TOP N問題呀，是不是腦海中不由自主的蹦出了排序算法啦~
哈哈，咱就按照這個思路走。然后，表面不慌，假裝思索中ing，其實內(nèi)心再想：排序算法是啥呀？

這里簡單提下：

冒泡排序，核心思想：相鄰比較。每次將最大的浮出水面。

快速排序，核心思想：分治法+挖坑填數(shù)。每次選擇一基數(shù)，排序完成左邊比基數(shù)小，右邊比基數(shù)大。一直切分（分治），直至選出無序的最大的N個整數(shù)。

堆排序（出場自帶豬腳光環(huán)~），可以創(chuàng)建一個N大小的最小堆。然后balabala。

這時候你可能要打斷一下了:啥？最小堆？我這是要選出最大的N個元素呀？有木有搞錯？emmm等等，啥叫堆？？？啥叫最小堆？？？為什么不選最大堆呢？？？

請聽我戲說一下：

基礎(chǔ)概念：

堆：分為最大堆和最小堆，其實就是完全二叉樹，最大堆要求父節(jié)點的元素都大于等于子節(jié)點，最小堆要求父節(jié)點元素小于等于子節(jié)點。

下面圖解下如何生成大根堆：

我就拿（內(nèi)心PS：讀書人的事情，怎么能說偷呢？）一下圖吧，放在這里這里讓大家容易理解~~
給定一個列表array=[16,7,3,20,17,8]，對其進行堆排序。
首先根據(jù)該數(shù)組元素構(gòu)建一個完全二叉樹，得到

原始的數(shù)據(jù)堆

然后需要構(gòu)造初始堆，則從最后一個非葉節(jié)點開始調(diào)整，調(diào)整過程如下：

第一步：找到最后一個組（非葉節(jié)點），左節(jié)點8 pk 擂主3，左孩子8勝利！然后3和8互相調(diào)換位置。敗者3沒有子節(jié)點，結(jié)束比賽。

小組賽第一場.png

從右到左。組內(nèi)pk，左子樹20 pk 右子樹17 左子樹20勝利，獲得挑戰(zhàn)擂主7的機會。左子樹20 pk 擂主7 左子樹20勝利，20和7交換位置。敗者7沒有子節(jié)點，結(jié)束比賽。

小組賽第二場

從下到上，左子樹20 PK 右子樹8，左子樹20勝利。獲得挑戰(zhàn)擂主16的機會。左子樹20 pk 擂主16 左子樹勝利，交換位置。
此時敗者16含有孩子節(jié)點，將被挑戰(zhàn)。

小組賽第三場！冠軍戰(zhàn)！

組內(nèi)挑戰(zhàn)開始：左子樹7和右子樹17組內(nèi)pk，右子樹17勝利。獲取挑戰(zhàn)擂主16的機會。右子樹17和擂主16pk，右子樹17勝利，交換位置。敗者16無孩子節(jié)點，結(jié)束比賽。

敗者挑戰(zhàn)賽

這樣就得到了初始堆。

哈哈，相信到這里，基本懂得同學(xué)還是懂，不懂得還是一臉XX。這是哪？我在干什么？你是誰？

咱們慢慢分析：

無序數(shù)組轉(zhuǎn)化為大根堆步驟：

1.找到最后一個非葉節(jié)點，從右到左，從下到上，遍歷所有非葉節(jié)點；

2.若是父節(jié)點小于最大的子節(jié)點，那么交換父子節(jié)點的位置，但是要注意，交換之后對其他節(jié)點的影響。

我們的目標是：
(沒有蛀牙....)根節(jié)點一定是樹中最大的值。同時，父節(jié)點大于子節(jié)點。

切回到我們的問題。此時，你應(yīng)該基本知道了堆的概念，為什么不選最大堆呢？因為咱們選最小堆就是采用末位淘汰制。將堆中最小元素剔除。
每次最小堆調(diào)整后，總會將整個堆中最小的元素放在根節(jié)點上，然后我們分別取出[N-1,M]中的元素，若大于堆頂，則替換。然后（隨著堆的蠕動，你可以動態(tài)想想這個畫面~~）再次將最小元素選出放于堆頂。直至堆里保存的都是最大的元素。

此時，你會想怎么細節(jié)怎么實現(xiàn)的：如何確定最后一個非葉節(jié)點呢？如何精確找到每一個孩子節(jié)點呢？

嘿嘿，我可真是一個小機靈鬼...，放心，全都給你整的明明白白的~

如何確定父節(jié)點和子節(jié)點的下標位置呢？

(1) 它的左孩子結(jié)點是：R[2i+1];
(2) 它的右孩子結(jié)點是：R[2i+2];
(3) 它的父結(jié)點是：R[(i-1)/2];

騙誰呢？具體解釋下，不要粘貼公式糊弄你的小可愛們！哼~

那好，咱們從零分析一下：

還是上面的數(shù)組，證據(jù)在上面，咱們就開始分析啦：

array=[16,7,3,20,17,8] 一個長度為6的數(shù)組。

咱們從i=5，最后一個元素array[5]開始說起：
父節(jié)點：(i-1)/2=2，他的父節(jié)點就是i=2，array[2]也就是3。
子節(jié)點：2i+1=11，等等兄得，你越界了...你根本沒有孩子節(jié)點...(名偵探小胖)
于是我就大膽推測一下，最后一個非子節(jié)點就是array[2]。

反向推理一下：i=2時，左孩子：2i+1=5，右孩子：2i+2=6，但是最大下標是5，那么只有一個孩子節(jié)點array[5]也就是8。

那倒數(shù)第二個下標非葉節(jié)點的下標是啥？
博主內(nèi)心獨白：emmm我也不知道....繼續(xù)套公式，看看有啥規(guī)律不。

數(shù)組倒數(shù)第二個下標數(shù)是i=4，(i-1)/2=1，那么下標array[1]就是第2個父節(jié)點。
數(shù)組倒數(shù)第三個下標數(shù)是i=3，(i-1)/2=1，也是下標array[1]。

那倒數(shù)第一個下標非葉節(jié)點的下標是啥？
數(shù)組倒數(shù)第四個下標數(shù)是i=2，(i-1)/2=1，那么下標array[0]就是第3個父節(jié)點。
數(shù)組倒數(shù)第三個下標數(shù)是i=1，(i-1)/2=1，也是下標array[0]。

此時還有嗎？
數(shù)組倒數(shù)第五個下標數(shù)是i=0，(i-1)/2=-1，也是下標array[-1]。

也就是根節(jié)點沒有父節(jié)點了....

等等，我好像發(fā)現(xiàn)啥規(guī)律了...
父節(jié)點是array[2]=3 array[1]=7 array[0]=16。
array=[16,7,3,20,17,8]

image

在我找到最后一個非葉節(jié)點 i 之后，通過i-1找到其他非葉節(jié)點，直到根節(jié)點的下標是0。

可是，概念太多，記不住呀。沒事，安排好了，結(jié)合一個生活場景，真正做到熟記于心~

結(jié)合生活場景解釋一下：

現(xiàn)在要開始 XX聯(lián)盟S17 的比賽，比賽組根據(jù)玩家投票新采用了一種新的比賽規(guī)則，規(guī)則如下：

橫向：每個新晉擂主可以參與更高一級的比賽，直至選出冠軍。登頂大根堆頂峰；

縱向：每個下臺擂主要被更低一級的選手挑戰(zhàn)，需要證明自己實力，也可能被一擼到底；

簡言之：能者上，弱者下
每一小組選出最強者，參與擂主pk，勝利者獲取下一次挑戰(zhàn)機會；失敗者要被挑戰(zhàn)，直至完成一場勝利，或者排名倒數(shù)。

   //比賽開始-請各小組按順序進行比賽（從排名最后一個小組開始）
public static int[] createMaxHeap(int[] arr) {
   int length = arr.length;
    //冠軍下標是0
    for (int i = (length - 1-1) / 2; i >= 0; i--) {
        //開啟小組擂臺賽
        doJustHeapMove(arr, i, length);
    }
    return arr;
}

而后，開始了激烈的小組比賽，擂主先把收拾自己的東西，因為他也不知道自己是一敗涂地還是保持原位！心里有些忐忑~

//小組擂臺開始
private static void doJustHeapMove(int[] arr, int root, int length) {
    int temp = arr[root];  //擂主將自己的東西保存好

    //確定小組成員，確保每一個人都有機會挑戰(zhàn)（最后元素:length-1）
    //若發(fā)起挑戰(zhàn)，擂主失敗，那么就會子節(jié)點挑戰(zhàn)
    //每次開始，均獲取到小組成員編號（而開始的root若是挑戰(zhàn)失敗，便成為了lChild）
    for (int lChild = 2 * root + 1; lChild < length; lChild = 2 * lChild + 1) {
        //判斷左節(jié)點是否是length-2，即不是最后一個元素！
        //若是最后一個元素，小組只有自己，直接參與擂臺賽
        //選出小組最強者，準備參與擂主pk，
        if (lChild < length - 1 && arr[lChild + 1] > arr[lChild]) {
            lChild++;
        }
        //擂臺賽開始
        if (temp >= arr[lChild]) {
            break;  //小組擂臺賽結(jié)束，開始下一小組的比賽
        } else {
            arr[root] = arr[lChild];  //成員升級（擂主）
            root = lChild;   //擂主降級（獲取到降級的編號）
        }
    }
    //擂主降級賽結(jié)束，灰溜溜的走了~
    arr[root] = temp;
}

我還會回來的(擂主內(nèi)心獨白)~~

力扣解法

215. 數(shù)組中的第K個最大元素

兜兜轉(zhuǎn)轉(zhuǎn)，從第一篇博客到2021.08.22已經(jīng)過去了2年半多了。今天又回到這個題目。帶來一種最小堆更加簡潔的實現(xiàn)。即依賴JDK API來實現(xiàn)最小堆，只需要使得最小堆維護top n個元素即可。

class Solution {
    /**
     * 最小堆實現(xiàn)TOP N
     */
    public int findKthLargest(int[] nums, int k) {
        //定義的最小堆
        PriorityQueue<Integer> queue = new PriorityQueue<>(k, (a, b) -> a - b);

        //最小堆，先入k個元素
        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();
    }
}