溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
Java優先隊列是怎樣的，很多新手對此不是很清楚，為了幫助大家解決這個難題，下面小編將為大家詳細講解，有這方面需求的人可以來學習下，希望你能有所收獲。
優先隊列（priority queue）是一種特殊的數據結構。
隊列中每一個元素都被分配到一個優先權值，出隊順序按照優先權值來劃分。
一般有兩種出隊順序：高優先權出隊或低優先權出隊。priority queue至少要有兩個最基本的ADT：進隊，出隊（按照高優先權或低優先權）
產生原因：同樣是為了提高數據處理的效率。試想，要實現優先隊列對應的功能，若使用鏈表或者數組，那么要么先排序再插入，要么先插入再查找最大最小元素。這樣一來，入隊出隊的時間復雜度至少為O(N)。
優先隊列出隊和入隊的時間復雜度均為O(log N)。
優先隊列基于二叉堆實現。
堆是一種特殊的二叉樹，性質如下：
每個結點的值都大于或等于其左右孩子結點的值（大頂堆），或每個結點的值都小宇或等于其左右孩子的值（小頂堆）。
必須滿足完全二叉樹的結構。
完全二叉樹 complete binary tree
葉節點只可能出現在最后兩層，且最后一層的葉節點都左對齊
一棵深度為h的完全二叉樹
滿二叉樹 full binary tree
深度為h的滿二叉樹有（2^h）-1個結點
由二叉堆的定義可以看出，跟結點一定是二叉堆中結點值最大（或最小）的。較大（或較小）的結點靠近根節點
堆的存儲結構：
一般情況下，堆用數組來存儲，第i個結點的父節點的下標就是（i-1）/2.
如果用層序遍歷順序將大頂堆和小頂堆存入數組，
則關系如圖：
插入：插入一個元素之后，新元素首先被插入表層（即最后一層盡可能左邊的位置），之后再根據堆的性質進行調整。
例：寫出一次一個地將10,12,1,14,6,5,8,15,3,9,7,4,11,13和2插入一個初始為空的二叉堆的結果
刪除：刪除總是發生在根處，之后將最后一個元素（即最后一層最右邊的元素）拿來填補空缺，之后根據堆的性質進行調整堆的結構。
看完上述內容是否對您有幫助呢？如果還想對相關知識有進一步的了解或閱讀更多相關文章，請關注億速云行業資訊頻道，感謝您對億速云的支持。
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
