一、基本定義與特性

1. 本質(zhì)：PriorityQueue 是 Java 集合框架中 Queue 接口的實(shí)現(xiàn)類(lèi)，基于堆（Heap） 數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)（默認(rèn)是最小堆），底層通過(guò)數(shù)組存儲(chǔ)元素。
2. 核心特性：
   • 隊(duì)列中的元素會(huì)按照優(yōu)先級(jí)順序出隊(duì)，而非先進(jìn)先出（FIFO）；
   • 不允許存儲(chǔ) null 元素；
   • 非線程安全，多線程場(chǎng)景需使用 PriorityBlockingQueue；
   • 容量可自動(dòng)擴(kuò)容（默認(rèn)初始容量為 11，擴(kuò)容規(guī)則：容量 < 64 時(shí)翻倍，≥64 時(shí)擴(kuò)容 50%）；
   • 迭代器遍歷的結(jié)果不保證有序，僅出隊(duì)（poll()/remove()）時(shí)保證優(yōu)先級(jí)順序。

二、關(guān)于堆

1.優(yōu)先級(jí)規(guī)則 ↔ 堆的類(lèi)型

• PriorityQueue默認(rèn)實(shí)現(xiàn)最小堆：依賴(lài)元素的 Comparable 接口（compareTo() 定義自然順序），本質(zhì)是維護(hù)最小堆的堆序性；
• 自定義優(yōu)先級(jí)（如最大堆）：傳入 Comparator 比較器，本質(zhì)是修改堆的 “堆序性判斷邏輯”，例如：

// 最大堆：Comparator修改siftUp/siftDown的比較規(guī)則，讓父節(jié)點(diǎn)≥子節(jié)點(diǎn)
PriorityQueue<Integer> maxHeap = new PriorityQueue<>((a, b) -> b - a);

• 異常根源：若元素未實(shí)現(xiàn) Comparable 且無(wú) Comparator，堆序性無(wú)法判斷，運(yùn)行時(shí)拋 ClassCastException。

2. 存儲(chǔ)結(jié)構(gòu) ↔ 堆的數(shù)組存儲(chǔ)

• PriorityQueue 底層直接復(fù)用堆的數(shù)組存儲(chǔ)邏輯：
  • 初始容量 11（數(shù)組初始長(zhǎng)度），擴(kuò)容規(guī)則：容量 < 64 時(shí)翻倍，≥64 時(shí)擴(kuò)容 50%（堆的數(shù)組存儲(chǔ)需要連續(xù)空間，擴(kuò)容是為了滿(mǎn)足堆的動(dòng)態(tài)插入）；
  • 空隊(duì)列時(shí)數(shù)組為默認(rèn)空數(shù)組，添加第一個(gè)元素時(shí)初始化長(zhǎng)度為 11。

3. 核心方法 ↔ 堆的核心操作

PriorityQueue 的所有核心方法，本質(zhì)都是調(diào)用堆的插入 / 刪除 / 堆化操作：

        堆的存儲(chǔ)是基于數(shù)組的完全二叉樹(shù)映射—— 利用完全二叉樹(shù) “層序排列無(wú)空洞” 的特性，將樹(shù)節(jié)點(diǎn)按層序順序存入數(shù)組，無(wú)需額外存儲(chǔ)指針（如鏈?zhǔn)酱鎯?chǔ)），空間效率和索引計(jì)算效率極高，這也是 Java PriorityQueue 底層選擇數(shù)組存儲(chǔ)堆的核心原因。

4.存儲(chǔ)核心原理

1. 為什么選數(shù)組？堆的本質(zhì)是完全二叉樹(shù)（除最后一層外，每一層節(jié)點(diǎn)數(shù)都滿(mǎn)；最后一層節(jié)點(diǎn)靠左排列），這種結(jié)構(gòu)的節(jié)點(diǎn)可以通過(guò) “層序遍歷” 的順序無(wú)間隙地填入數(shù)組，且父 / 子節(jié)點(diǎn)的索引可通過(guò)簡(jiǎn)單數(shù)學(xué)公式計(jì)算，無(wú)需像普通二叉樹(shù)那樣存儲(chǔ)左 / 右子節(jié)點(diǎn)指針，空間利用率接近 100%。
2. 核心映射規(guī)則（必記）假設(shè)堆的底層數(shù)組為 queue，節(jié)點(diǎn)的數(shù)組索引為 i（從 0 開(kāi)始），則：

   

5.可視化示例（最小堆）

以最小堆 [1, 3, 8, 5, 4] 為例，完全二叉樹(shù)結(jié)構(gòu)與數(shù)組存儲(chǔ)的對(duì)應(yīng)關(guān)系：

        1 (索引0)  ← 堆頂
       /  \
      3(1) 8(2)
     /  \
    5(3) 4(4)

對(duì)應(yīng)的底層數(shù)組 queue = [1, 3, 8, 5, 4]，驗(yàn)證映射規(guī)則：

• 索引 1（節(jié)點(diǎn) 3）的父節(jié)點(diǎn)：(1-1)/2 = 0（節(jié)點(diǎn) 1）；
• 索引 0（節(jié)點(diǎn) 1）的左子節(jié)點(diǎn)：2*0+1=1（節(jié)點(diǎn) 3），右子節(jié)點(diǎn)：2*0+2=2（節(jié)點(diǎn) 8）；
• 索引 3（節(jié)點(diǎn) 5）的父節(jié)點(diǎn)：(3-1)/2=1（節(jié)點(diǎn) 3），無(wú)左右子節(jié)點(diǎn)（2*3+1=7 ≥ 5）。

6.關(guān)鍵節(jié)點(diǎn)類(lèi)型的索引判斷（堆操作的基礎(chǔ)）

基于數(shù)組存儲(chǔ)的特性，可快速判斷節(jié)點(diǎn)類(lèi)型，這是堆化、siftUp/siftDown 的核心依據(jù)：

1. 葉子節(jié)點(diǎn)：索引范圍 [size/2, size-1]（size 為堆的元素個(gè)數(shù)）；示例：上述堆 size=5，葉子節(jié)點(diǎn)索引為 [2,4]（節(jié)點(diǎn) 8、5、4），葉子節(jié)點(diǎn)無(wú)需執(zhí)行 siftDown（無(wú)后代可比較）。
2. 非葉子節(jié)點(diǎn)：索引范圍 [0, size/2 - 1]；示例：size=5，非葉子節(jié)點(diǎn)索引為 [0,1]（節(jié)點(diǎn) 1、3），堆化時(shí)僅需遍歷這些節(jié)點(diǎn)執(zhí)行 siftDown。

7.關(guān)于siftUp/siftDown

        siftUp（向上調(diào)整） 和 siftDown（向下調(diào)整），二者是堆（優(yōu)先隊(duì)列底層）維護(hù)「堆序性」的核心操作

        總結(jié)：siftUp 是「自下而上」找位置（插入用），siftDown 是「自上而下」找位置（刪堆頂 / 堆化用），最終都是為了讓堆滿(mǎn)足「最小 / 最大堆」的核心規(guī)則。

8.建堆的時(shí)間復(fù)雜度

建堆（heapify）的時(shí)間復(fù)雜度是 O(n)（而非直覺(jué)上的 O (n log n)），這是堆操作中極易混淆的關(guān)鍵點(diǎn)，以下用「結(jié)論 + 原理 + 對(duì)比」講清楚：

8.1核心結(jié)論

8.2為什么堆化是 O (n)？（通俗推導(dǎo)）

堆化的核心是「從最后一個(gè)非葉子節(jié)點(diǎn)反向遍歷，執(zhí)行 siftDown」，不同層級(jí)的節(jié)點(diǎn)執(zhí)行 siftDown 的次數(shù)不同，葉子節(jié)點(diǎn)甚至無(wú)需調(diào)整，整體操作次數(shù)遠(yuǎn)低于 O (n log n)：

1. 堆的結(jié)構(gòu)基礎(chǔ)：堆是完全二叉樹(shù)，假設(shè)堆的高度為h（根節(jié)點(diǎn)層級(jí)為 0，葉子節(jié)點(diǎn)層級(jí)為h），節(jié)點(diǎn)總數(shù)n ≈ 2^(h+1) - 1；
2. 分層計(jì)算操作次數(shù)：
   • 層級(jí)k的節(jié)點(diǎn)數(shù)：2^k 個(gè)；
   • 該層級(jí)節(jié)點(diǎn)執(zhí)行 siftDown 的最大次數(shù)：h - k（越靠近根節(jié)點(diǎn)，需要向下調(diào)整的次數(shù)越多；葉子節(jié)點(diǎn)層級(jí)h，調(diào)整次數(shù)為 0）；
3. 總操作次數(shù)求和：總次數(shù) = 2^0*(h) + 2^1*(h-1) + 2^2*(h-2) + ... + 2^(h-1)*1；數(shù)學(xué)求和后可推導(dǎo)：總次數(shù) ≈ 2n（收斂到 O (n)）。

8.3對(duì)比理解（為什么不是 O (n log n)？）

如果用「逐個(gè) offer 元素（每次 siftUp）」的方式建堆，時(shí)間復(fù)雜度是 O (n log n)：

• 每個(gè)元素插入時(shí)，最多需要從葉子節(jié)點(diǎn)調(diào)整到根節(jié)點(diǎn)（最多h=log n次操作）；
• n個(gè)元素總操作次數(shù) = n * log n，即 O (n log n)。

而堆化用 siftDown，僅非葉子節(jié)點(diǎn)需要調(diào)整，且越靠近葉子的節(jié)點(diǎn)調(diào)整次數(shù)越少，整體效率遠(yuǎn)高于逐個(gè)插入 —— 這也是 PriorityQueue 初始化集合時(shí)選擇 heapify（而非循環(huán) offer）的核心原因。

總結(jié)：堆化（O (n)）是「批量?jī)?yōu)化版」建堆，利用完全二叉樹(shù)的層級(jí)特性減少無(wú)效調(diào)整；逐個(gè)插入（O (n log n)）是「動(dòng)態(tài)零散版」，無(wú)批量?jī)?yōu)化，效率更低。

三、堆（PriorityQueue）常用接口 / API 全解析

Java 中堆的操作完全通過(guò) PriorityQueue 類(lèi)暴露（實(shí)現(xiàn) Queue 接口），以下是開(kāi)發(fā)中最常用的接口，按「核心操作、查詢(xún)操作、輔助操作」分類(lèi)，結(jié)合堆的底層邏輯講解（默認(rèn)最小堆，最大堆僅比較器不同）：

1.接口體系背景

   PriorityQueue 實(shí)現(xiàn)了 java.util.Queue 接口，間接繼承 Collection/Iterable，所有接口均圍繞「堆的核心特性（堆頂為極值、O (log n) 插入 / 刪除）」設(shè)計(jì)，底層關(guān)聯(lián) siftUp/siftDown 等堆操作。

2.核心操作（堆的插入 / 刪除）

3.輔助操作（堆的清空 / 遍歷）

總結(jié) 

到此這篇關(guān)于Java優(yōu)先隊(duì)列PriorityQueue的文章就介紹到這了,更多相關(guān)Java優(yōu)先隊(duì)列PriorityQueue內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評(píng)論