面試官：寫一個堆排吧
我心想：堆排是什么鬼
理解堆排，首先要理解二叉堆，理解了二叉堆的“下沉”操作，基本上就可以理解堆排了，今天我們來看一看什么是堆，以及堆的一般操作
一、優先級佇列
近日，一塵遇到了煩心事，于是找老師去訴苦了
一塵列了幾個要做的事
一塵道出了心中的苦
慧能：你可以做優先級最高的事情，做完后洗掉它，然后做剩下優先級最高的事，當然，很有可能有其他事插入進來，新插入的事情如果優先級不是最高，就不做，這樣你就一直做優先級最高的事了
接著慧能順手畫了一個圖
優先級佇列中每個元素都有優先級，優先級最高的最先被處理
二、優先級佇列的實作
一塵非常想知道黑盒里面是什么
然后我把優先級存入一個無序陣列里，取出的時候遍歷陣列一邊，找出最小值，插入的時候直接插到集合末尾
一塵畫了一幅圖解釋道
隨后，一塵又畫出了插入6后的圖
三、堆
這里我們只討論二叉堆，把二叉堆稱為堆，堆也有d-堆，左式堆等等
慧能看一塵不是很明白，順手畫了個圖
慧能畫了一個二叉堆實體
注意：二叉堆中兩個孩子之前的大小沒有關系，可能左孩子>=右孩子，也可能右>=左
慧能隨手畫了一個小根堆和一個大根堆
本文討論小根堆
4、插入操作
每個父節點的值小于等于其左右孩子的值被稱為堆的有序性，另一種情況是大于等于也稱之為堆的有序性
慧能隨手畫了一個插入操作破壞堆有序性的圖
說完，慧能飛速地寫出了上浮的代碼
一塵暗自驚嘆老師的代碼功力
五、洗掉操作
一塵聽完此話緊張的手心出汗，但還是硬著頭皮想了想，突然靈光一現
隨后一塵畫出了交換后的圖
一塵剛松了口氣，誰知還要寫代碼，只見一塵想了想，寫寫擦擦好幾遍最終寫下了如下代碼
如圖
只見一塵又寫了一段代碼
leftIndex = 2*parentIndex;
rightIndex = 2*parentIndex+1;
看來以后得好好學資料結構與演算法了，不然連時間都管理不好，一塵心想
另外，演算法的學習也是必經之路，這里給大家推薦一個大佬的刷題筆記
帥地校招就是刷了這份筆記來應付面試官的，這里分享給大家吧，
下載鏈接：BAT大佬的刷題筆記太經典
把這份筆記突擊學習一下，很多演算法考察，基本都穩了
另外，再給大家推薦一份某大佬的 leetcode 刷題筆記，匯聚了上千道 leetcode 題解，并且代碼都是 beat 100%：
下載鏈接：leetcode 分類題解（最優解）
就算你現在不學演算法，那么這份筆記也值得你收藏，萬一有人問你 Leetcode 某道題解，或者有大神在討論題解，咱打開這份筆記，不管三七二十一，直接把最優解扔給他，然后退出群聊
額外話
堆排序的實作就是基于二叉堆的，堆排序是十大排序演算法中必學的一種排序演算法，這里帥地給大家找來了優質的學習文章供大家學習，網上其他文章質量參差不齊，詳細經過帥地挑選的這些文章能夠節省你不少時間
漫畫：什么是冒泡排序演算法？
漫畫：什么是選擇排序演算法？
漫畫：什么是插入排序演算法？
漫畫：什么是希爾排序演算法？
漫畫：什么是歸并排序演算法？
漫畫：什么是快速排序演算法？
漫畫：什么是堆排序演算法？
漫畫：為什么說O(n)復雜度的基數排序沒有快速排序快？
什么是計數排序演算法？
十大排序演算法極簡匯總篇
作者簡潔
作者：大家好，我是帥地，從大學、自學一路走來，深知演算法，計算機基礎知識的重要性，公眾號「帥地玩編程」10萬粉絲作者，專業于寫這些底層知識，提升我們的內功，帥地期待你的關注，和我一起學習，點擊了解我四年大學學 習之路 轉載說明：未獲得授權，禁止轉載
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/281252.html
標籤：其他
上一篇：C語言基礎