從構造方法到實踐練習優先隊列
一.導言
我們之前討論過堆棧和隊列。在java中，棧的類是stack，隊列的接口是queue。我們通過queue的實現類LinkedList練習了queue的方法，並利用相關知識完成了LeetCode 232題如何用棧實現queue。
大家都知道，像我這種不思進取的人，怎麼會突然有想法去學一門在工作中從未用過的課呢？不奇怪，我在做LeetCode 347的時候。Top K高頻元素題今天試了幾次不知道怎麼做。看了一下評論部分，發現這個問題其實應該是用優先級隊列來做的，才知道有優先級隊列這種東西。
但是，PriorityQueue在某些編程語言中是找不到的。幸運的是，java有。實現優先級隊列的類是優先級隊列。顧名思義，優先就是優先的意思。
俗話説，很多東西用了才知道。所以今天，我將和你一起玩這個優先隊列。
第二，優先級隊列
由於我沒有下載java8的源代碼，PriorityQueue類裏有很多英文註釋，不方便截圖，所以我就直接把代碼放在下面了。
什麼是優先級隊列？
眾所周知，放入一個元素是放在隊列的末尾，放入一個元素就是取出隊列頭的元素，也就是我們常説的FIFO。那麼什麼是優先級隊列呢？排隊和排隊有什麼區別？能解決什麼樣的問題？
優先級隊列仍然是顧名思義。優先級隊列將根據元素的權重自動排列。也就是説，優先級隊列實際上是有反FIFO規則的，但其對外接口仍然是從隊列頭取元素，在隊列尾加元素，沒有其他訪問方式。它看起來像一個隊列。
隊列實際上是一個覆蓋着隊列皮膚的堆。
什麼是堆？
Heap通常可以看作一個完整二叉樹的數組對象，樹中的每個節點不小於(或大於)其左右子節點的值。
如果父節點大於左右子節點的值，則為大頂堆。
如果父節點小於左右子節點的值，則它是一個小的頂部堆。
優先級隊列的特徵
優先級隊列中的元素必須實現內部比較器或外部比較器。
優先級隊列具有小頂堆的所有特徵，默認為小頂堆。
優先級隊列不是線程安全的。
不允許空元素。
隊列本身是無序的，但是提取的元素的順序是有序的。
部分功能來自百度。如有疑問，歡迎評論指正。謝謝你。
基本屬性
//序列化相關，可以忽略
private static final long serialVersionUID =-7720805057305804111 l；
//默認情況下沒有構造參數時數組的長度
private static final int DEFAULT _ INITIAL _ CAPACITY = 11；
//存儲元素的數組隊列
瞬態對象[]隊列；
//
private int size = 0；
//設置排序策略
私有最終比較器
//
瞬態int mod count = 0；複製代碼
施工方法
我將以下三種構造方法歸為一類，第四種構造方法為主，其他三種為方法重載，DEFAULT_INITIAL_CAPACITY為值。隊列長度比較器參考優先級排序規則。默認情況下，優先級值很小。
第四種構造方法是初始化隊列數組的長度，設置比較器。
公共優先級隊列(){
this(DEFAULT_INITIAL_CAPACITY，null)；
}
公共優先級隊列(int initialCapacity) {
this(initialCapacity，null)；
}
公共優先級隊列(比較器
this(DEFAULT_INITIAL_CAPACITY，比較器)；
}
公共優先級隊列(int initialCapacity，
比較儀
if (initialCapacity < 1)
拋出新的IllegalArgumentException()；
this . queue = new Object[initial capacity]；
this.comparator =比較器；
}
複製代碼
下面是PriorityQueue構造方法的一個測試。可以發現，當我們調用PriorityQueue.size()方法時，返回的不是我們設置的隊列長度，而是元素個數。
下面的施工方法會稍微複雜一點。
//包含優先級元素
公共優先級隊列(PriorityQueue
this .比較器=(比較器
initfromporityqueue(c)；
}複製代碼
是上面的構造函數構造的，真的很有意思。大家可以看到，priorityQueue4是按照我們設定的規則降序排列的，沒有任何問題。但是priorityQueue5繼承了priorityQueue4和比較器的元素後，打印出來的並沒有完全按順序打印，最後四個元素變成了2，1，2，1，2，2，1。
用指定順序的集合元素創建`PriorityQueue。`
公共優先級隊列(排序集
this .比較器=(比較器
initElementsFromCollection(c)；
}複製代碼
具體的測試代碼如下所示。像PriorityQueue類一樣，它是一個繼承其類的比較器。
下面的構造方法整合了前面兩個構造方法，他們調用的最後一個方法主要是初始化數組，有各種跳轉。有興趣的可以自己看看。
公共優先級隊列(集合
if (c已排序集合的實例){
有序集
this .比較器=(比較器
initElementsFromCollection(ss)；
}
else if(c instance of priority queue){
優先級隊列
this .比較器=(比較器
initfromporityqueue(pq)；
}
否則{
this.comparator = null
initFromCollection(c)；
}
}複製代碼
常規方法
添加/提供:添加元素
Element/peek:不刪除return元素。
Remove/poll:彈出元素並刪除。
刪除:刪除元素，如果有多個元素，則只刪除一個元素。
摘要
有很多東西，你用了才知道。如果可以的話，最好提前瞭解他們，防止出現我這樣的情況:不知道什麼時候需要他們。
有什麼説法？你用一本書就不那麼討厭了。走吧。
