上一篇的 「Java 集合框架」里，還剩下一個大問題沒有說的，那就是 PriorityQueue，優先佇列，也就是堆，Heap，
什么是堆？
堆其實就是一種特殊的佇列——優先佇列，
普通的佇列游戲規則很簡單：就是先進先出；但這種優先佇列搞特殊，不是按照進佇列的時間順序，而是按照每個元素的優先級來比拼，優先級高的在堆頂，
這也很容易理解吧，比如各種軟體都有會員制度，某軟體用了會員就能加速下載的，不同等級的會員速度還不一樣，那就是優先級不同呀，
還有其實每個人回復微信訊息也是默默的把訊息放進堆里排個序：先回男朋友女朋友的，然后再回其他人的，
這里要區別于作業系統里的那個“堆”，這兩個雖然都叫堆，但是沒有半毛錢關系，都是借用了 Heap 這個英文單詞而已，
我們再來回顧一下「堆」在整個 Java 集合框架中的位置：
也就是說，
PriorityQueue 是一個類 (class)； PriorityQueue 繼承自 Queue 這個介面 (Interface)；
那 heap 在哪呢？
heap 其實是一個抽象的資料結構，或者說是邏輯上的資料結構，并不是一個物理上真實存在的資料結構，
heap 其實有很多種實作方式，比如 binomial heap, Fibonacci heap 等等，但是面試最常考的，也是最經典的，就是 binary heap 二叉堆，也就是用一棵完全二叉樹來實作的，
那完全二叉樹是怎么實作的？
其實是用陣列來實作的！
所以 binary heap/PriorityQueue 實際上是用陣列來實作的，
這個陣列的排列方式有點特別，因為它總會維護你定義的（或者默認的）優先級最高的元素在陣列的首位，所以不是隨便一個陣列都叫「堆」，實際上，它在你心里，應該是一棵「完全二叉樹」，
這棵完全二叉樹，只存在你心里和各大書本上；實際在在記憶體里，哪有什么樹？就是陣列罷了，
那為什么完全二叉樹可以用陣列來實作？是不是所有的樹都能用陣列來實作？
這個就涉及完全二叉樹的性質了，我們下一篇會細講，簡單來說，因為完全二叉樹的定義要求了它在層序遍歷的時候沒有氣泡，也就是連續存盤的，所以可以用陣列來存放；第二個問題當然是否，
堆的特點
堆是一棵完全二叉樹；
堆序性 (heap order): 任意節點都優于它的所有孩子，
a. 如果是任意節點都大于它的所有孩子，這樣的堆叫大頂堆，Max Heap;
b. 如果是任意節點都小于它的所有孩子，這樣的堆叫小頂堆，Min Heap;
左圖是小頂堆，可以看出對于每個節點來說，都是小于它的所有孩子的，注意是所有孩子，包括孫子，曾孫...
既然堆是用陣列來實作的，那么我們可以找到每個節點和它的父母/孩子之間的關系，從而可以直接訪問到它們，
比如對于節點 3 來說，
它的 Index = 1， 它的 parent index = 0, 左孩子 left child index = 3, 右孩子 right child index = 4.
可以歸納出如下規律：
設當前節點的 index = x, 那么 parent index = (x-1)/2, 左孩子 left child index = 2*x + 1, 右孩子 right child index = 2*x + 2.
有些書上可能寫法稍有不同，是因為它們的陣列是從 1 開始的，而我這里陣列的下標是從 0 開始的，都是可以的，
這樣就可以從任意一個點，一步找到它的孫子、曾孫子，真的太方便了，在之后講具體操作時大家可以更深刻的體會到，
那有關堆的基本操作，以及為什么 heapify() 是 O(n) 的，我們之后再聊，
如果你喜歡這篇文章，記得給我點贊留言哦～你們的支持和認可，就是我創作的最大動力，我們下篇文章見！
我是小齊，紐約程式媛，終生學習者，每天晚上 9 點，云自習室里不見不散！
更多干貨文章見我的 Github: https://github.com/xiaoqi6666/NYCSDE
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/159283.html
標籤：其他
上一篇：Java開發手冊精華總結
下一篇：Java開發手冊精華總結