數(shù)據(jù)結(jié)構(gòu)是指數(shù)據(jù)的組織、管理和存儲格式，其使用目的是為了高效地訪問和修改數(shù)據(jù)。常見的數(shù)據(jù)結(jié)構(gòu)有數(shù)組、鏈表、棧、隊(duì)列、散列表（哈希表）、樹等。其中數(shù)組和鏈表可以看成是實(shí)實(shí)在在的物理結(jié)構(gòu)，其他數(shù)據(jù)結(jié)構(gòu)都可以看成是邏輯結(jié)構(gòu)，他們的物理實(shí)現(xiàn)既可以利用數(shù)組也可以利用鏈表來實(shí)現(xiàn)。
1、數(shù)組
數(shù)組是最為簡單常見的數(shù)據(jù)結(jié)構(gòu)，數(shù)組中的每個元素都有自己的下標(biāo)，元素在內(nèi)存中是順序存儲的，且內(nèi)存是由一個個連續(xù)的內(nèi)存單元組成的。
數(shù)組的優(yōu)勢在于讀取和更新元素，可以直接根據(jù)下標(biāo)讀取和更新元素，這種方式只花費(fèi)常數(shù)時間的復(fù)雜度。
在不改變元素相對位置的前提下，數(shù)組增加和刪除元素的操作都涉及到大量元素的被迫移動，其時間復(fù)雜度都是線性時間復(fù)雜度。
總之，數(shù)組適合讀操作多、寫操作少的場景。
2、鏈表
鏈表是一種在物理上非連續(xù)、非順序的數(shù)據(jù)結(jié)構(gòu)，由若干節(jié)點(diǎn)所組成，單向鏈表由存放數(shù)據(jù)的data部分和存放指向下一個節(jié)點(diǎn)的指針next部分所組成。而雙向鏈表由兩個指針，一個指向上一個節(jié)點(diǎn)，另一個指向下一個節(jié)點(diǎn)。
鏈表的優(yōu)勢在于能夠靈活地進(jìn)行插入和刪除操作。在查找元素時，鏈表不像數(shù)組那樣可以通過下標(biāo)快速進(jìn)行定位，只能從頭節(jié)點(diǎn)開始向后一個一個節(jié)點(diǎn)逐一查找，其時間復(fù)雜度為線性時間復(fù)雜度。更新元素前，需要先找到該元素，如果不考慮查找的過程，則鏈表更新元素的操作和數(shù)組一樣。
插入和刪除元素時，若不考慮之前查找元素的過程，只考慮純粹的插入和刪除操作，則時間復(fù)雜度都是常數(shù)級別的。
3、棧和隊(duì)列
3.1棧
棧是一種線性數(shù)據(jù)結(jié)構(gòu)，即可以利用數(shù)組實(shí)現(xiàn)，也可以利用鏈表實(shí)現(xiàn)。棧中的元素只能先進(jìn)后出，其基本操作為入棧（push）和出棧（pop），入棧和出棧只會影響到最后一個元素，所以無論棧是以數(shù)組還是以鏈表實(shí)現(xiàn)，入棧和出棧的時間復(fù)雜度都是常數(shù)級別的。
3.2隊(duì)列
隊(duì)列也是一種線性數(shù)據(jù)結(jié)構(gòu)，不同于棧的先進(jìn)后出，隊(duì)列中的元素只能先進(jìn)先出，隊(duì)列的出口端叫對頭，入口端叫隊(duì)尾。隊(duì)列既可以利用數(shù)組實(shí)現(xiàn)，也可以利用鏈表實(shí)現(xiàn)。
隊(duì)列的基本操作為入隊(duì)和出隊(duì)，對于鏈表實(shí)現(xiàn)方式，隊(duì)列的入隊(duì)和出隊(duì)操作和棧是大同小異的，而對于數(shù)組實(shí)現(xiàn)方式來說，采用了循環(huán)隊(duì)列的方式來維持隊(duì)列容量的恒定。
什么是循環(huán)隊(duì)列呢？
假設(shè)一個隊(duì)列經(jīng)過反復(fù)的入隊(duì)和出隊(duì)操作，還剩下2個元素，在“物理”上分布于數(shù)組的末尾位置。這時又有一個新元素將要入隊(duì)。
在數(shù)組不做擴(kuò)容的前提下，如何讓新元素入隊(duì)并確定新的隊(duì)尾位置呢？我們可以利用已出隊(duì)元素留下的空間，讓隊(duì)尾指針重新指回?cái)?shù)組的首位。
這樣一來，整個隊(duì)列的元素就“循環(huán)”起來了。在物理存儲上，隊(duì)尾的位置也可以在隊(duì)頭之前。當(dāng)再有元素入隊(duì)時，將其放入數(shù)組的首位，隊(duì)尾指針繼續(xù)后移即可。
一直到（隊(duì)尾下標(biāo)+1）%數(shù)組長度 = 隊(duì)頭下標(biāo)時，代表此隊(duì)列真的已經(jīng)滿了。需要注意的是，隊(duì)尾指針指向的位置永遠(yuǎn)空出1位，所以隊(duì)列最大容量比數(shù)組長度小1。
4、散列表（哈希表）
散列表也叫作哈希表（hash table），這種數(shù)據(jù)結(jié)構(gòu)提供了鍵（Key）和值（Value）的映射關(guān)系。只要給出一個Key，就可以高效查找到它所匹配的Value，時間復(fù)雜度接近于O(1)。可以說散列表是數(shù)組與鏈表的結(jié)合，它通過哈希函數(shù)實(shí)現(xiàn)Key和數(shù)組下標(biāo)的轉(zhuǎn)換，通過開放尋址法和鏈表法來解決哈希沖突。
4.1哈希函數(shù)
數(shù)組可以根據(jù)下標(biāo)進(jìn)行元素的隨機(jī)訪問，是一種查詢效率最高的數(shù)據(jù)結(jié)構(gòu)。散列表在本質(zhì)上也是一個數(shù)組，可是數(shù)組只能根據(jù)下標(biāo)，像a[0]、a[1]、a[2]、a[3]、a[4]這樣來訪問，而散列表的Key則是以字符串類型為主的。例如以學(xué)生的學(xué)號作為Key，輸入002123，查詢到李四；或者以單詞為Key，輸入by，查詢到數(shù)字46……
所以我們需要一個“中轉(zhuǎn)站”，通過某種方式，把Key和數(shù)組下標(biāo)進(jìn)行轉(zhuǎn)換。這個中轉(zhuǎn)站就叫作哈希函數(shù)。
在不同的語言中，哈希函數(shù)的實(shí)現(xiàn)方式是不一樣的。這里以Java的常用集合HashMap為例，來看一看哈希函數(shù)在Java中的實(shí)現(xiàn)。
在Java及大多數(shù)面向?qū)ο蟮恼Z言中，每一個對象都有屬于自己的hashcode，這個hashcode是區(qū)分不同對象的重要標(biāo)識。無論對象自身的類型是什么，它們的hashcode都是一個整型變量。
既然都是整型變量，想要轉(zhuǎn)化成數(shù)組的下標(biāo)也就不難實(shí)現(xiàn)了。最簡單的轉(zhuǎn)化方式是什么呢？是按照數(shù)組長度進(jìn)行取模運(yùn)算。
index = HashCode (Key) % Array.length
實(shí)際上，JDK（Java Development Kit，Java語言的軟件開發(fā)工具包）中的哈希函數(shù)并沒有直接采用取模運(yùn)算，而是利用了位運(yùn)算的方式來優(yōu)化性能。
通過哈希函數(shù)，我們可以把字符串或其他類型的Key，轉(zhuǎn)化成數(shù)組的下標(biāo)index。
如給出一個長度為8的數(shù)組，則當(dāng)
key=001121時，
index = HashCode ("001121") % Array.length = 1420036703 % 8 = 7
而當(dāng)key=this時，
index = HashCode ("this") % Array.length = 3559070 % 8 = 6
4.2寫操作的過程
寫操作就是在散列表中插入新的鍵值對（在JDK中叫作Entry）。
如調(diào)用hashMap.put("002931", "王五")，意思是插入一組Key為002931、Value為王五的鍵值對。
具體該怎么做呢？
第1步，通過哈希函數(shù)，把Key轉(zhuǎn)化成數(shù)組下標(biāo)5。
第2步，如果數(shù)組下標(biāo)5對應(yīng)的位置沒有元素，就把這個Entry填充到數(shù)組下標(biāo)5的位置。
但是，由于數(shù)組的長度是有限的，當(dāng)插入的Entry越來越多時，不同的Key通過哈希函數(shù)獲得的下標(biāo)有可能是相同的。例如002936這個Key對應(yīng)的數(shù)組下標(biāo)是2；002947這個Key對應(yīng)的數(shù)組下標(biāo)也是2。
這種情況，就叫作哈希沖突。
解決哈希沖突的方法主要有兩種，一種是開放尋址法，一種是鏈表法。
開放尋址法的原理很簡單，當(dāng)一個Key通過哈希函數(shù)獲得對應(yīng)的數(shù)組下標(biāo)已被占用時，我們可以“另謀高就”，尋找下一個空檔位置。
以上面的情況為例，Entry6通過哈希函數(shù)得到下標(biāo)2，該下標(biāo)在數(shù)組中已經(jīng)有了其他元素，那么就向后移動1位，看看數(shù)組下標(biāo)3的位置是否有空。
很不巧，下標(biāo)3也已經(jīng)被占用，那么就再向后移動1位，看看數(shù)組下標(biāo)4的位置是否有空。
幸運(yùn)的是，數(shù)組下標(biāo)4的位置還沒有被占用，因此把Entry6存入數(shù)組下標(biāo)4的位置。
這就是開放尋址法的基本思路。當(dāng)然，在遇到哈希沖突時，尋址方式有很多種，并不一定只是簡單地尋找當(dāng)前元素的后一個元素，這里只是舉一個簡單的示例而已。
在Java中，ThreadLocal所使用的就是開放尋址法。
接下來，重點(diǎn)講一下解決哈希沖突的另一種方法——鏈表法。這種方法被應(yīng)用在了Java的集合類HashMap當(dāng)中。
HashMap數(shù)組的每一個元素不僅是一個Entry對象，還是一個鏈表的頭節(jié)點(diǎn)。每一個Entry對象通過next指針指向它的下一個Entry節(jié)點(diǎn)。當(dāng)新來的Entry映射到與之沖突的數(shù)組位置時，只需要插入到對應(yīng)的鏈表中即可。
4.3讀操作的過程
讀操作就是通過給定的Key，在散列表中查找對應(yīng)的Value。
例如調(diào)用 hashMap.get("002936")，意思是查找Key為002936的Entry在散列表中所對應(yīng)的值。
具體該怎么做呢？下面以鏈表法為例來講一下。
第1步，通過哈希函數(shù)，把Key轉(zhuǎn)化成數(shù)組下標(biāo)2。
第2步，找到數(shù)組下標(biāo)2所對應(yīng)的元素，如果這個元素的Key是002936，那么就找到了；如果這個Key不是002936也沒關(guān)系，由于數(shù)組的每個元素都與一個鏈表對應(yīng)，我們可以順著鏈表慢慢往下找，看看能否找到與Key相匹配的節(jié)點(diǎn)。
在上圖中，首先查到的節(jié)點(diǎn)Entry6的Key是002947，和待查找的Key 002936不符。接著定位到鏈表下一個節(jié)點(diǎn)Entry1，發(fā)現(xiàn)Entry1的Key 002936正是我們要尋找的，所以返回Entry1的Value即可。
4.3散列表的擴(kuò)容
既然散列表是基于數(shù)組實(shí)現(xiàn)的，那么散列表也要涉及擴(kuò)容的問題。
首先，什么時候需要進(jìn)行擴(kuò)容呢？
當(dāng)經(jīng)過多次元素插入，散列表達(dá)到一定飽和度時，Key映射位置發(fā)生沖突的概率會逐漸提高。這樣一來，大量元素?fù)頂D在相同的數(shù)組下標(biāo)位置，形成很長的鏈表，對后續(xù)插入操作和查詢操作的性能都有很大影響。
這時，散列表就需要擴(kuò)展它的長度，也就是進(jìn)行擴(kuò)容。
對于JDK中的散列表實(shí)現(xiàn)類HashMap來說，影響其擴(kuò)容的因素有兩個。
Capacity，即HashMap的當(dāng)前長度
LoadFactor，即HashMap的負(fù)載因子，默認(rèn)值為0.75f
衡量HashMap需要進(jìn)行擴(kuò)容的條件如下。
HashMap.Size >= Capacity×LoadFactor
擴(kuò)容不是簡單地把散列表的長度擴(kuò)大，而是經(jīng)歷了下面兩個步驟。
1．擴(kuò)容，創(chuàng)建一個新的Entry空數(shù)組，長度是原數(shù)組的2倍。
2．重新Hash，遍歷原Entry數(shù)組，把所有的Entry重新Hash到新數(shù)組中。為什么要重新Hash呢？因?yàn)殚L度擴(kuò)大以后，Hash的規(guī)則也隨之改變。
經(jīng)過擴(kuò)容，原本擁擠的散列表重新變得稀疏，原有的Entry也重新得到了盡可能均勻的分配。
擴(kuò)容前的HashMap：
擴(kuò)容后的HashMap：
需要注意的是，關(guān)于HashMap的實(shí)現(xiàn)，JDK 8和以前的版本有著很大的不同。當(dāng)多個Entry被Hash到同一個數(shù)組下標(biāo)位置時，為了提升插入和查找的效率，HashMap會把Entry的鏈表轉(zhuǎn)化為紅黑樹這種數(shù)據(jù)結(jié)構(gòu)。
5、樹
在實(shí)際場景中，有許多邏輯關(guān)系并不是簡單的線性關(guān)系，常常存在著一對多，甚至是多對多的情況。其中樹和圖就是典型的非線性數(shù)據(jù)結(jié)構(gòu)。下面主要介紹一種典型的樹——二叉樹。二叉樹（binary tree）是樹的一種特殊形式。二叉，顧名思義，這種樹的每個節(jié)點(diǎn)最多有2個孩子節(jié)點(diǎn)。注意，這里是最多有2個，也可能只有1個，或者沒有孩子節(jié)點(diǎn)。
二叉樹的結(jié)構(gòu)如圖所示。
5.1滿二叉樹與完全二叉樹
此外，二叉樹還有兩種特殊形式，一個叫作滿二叉樹，另一個叫作完全二叉樹。
什么是滿二叉樹呢？
一個二叉樹的所有非葉子節(jié)點(diǎn)都存在左右孩子，并且所有葉子節(jié)點(diǎn)都在同一層級上，那么這個樹就是滿二叉樹。
簡單點(diǎn)說，滿二叉樹的每一個分支都是滿的。
什么又是完全二叉樹呢？
完全二叉樹的定義很有意思。對一個有n個節(jié)點(diǎn)的二叉樹，按層級順序編號，則所有節(jié)點(diǎn)的編號為從1到n。如果這個樹所有節(jié)點(diǎn)和同樣深度的滿二叉樹的編號為從1到n的節(jié)點(diǎn)位置相同，則這個二叉樹為完全二叉樹。
這個定義還真繞，看看下圖就很容易理解了。
在上圖中，二叉樹編號從1到12的12個節(jié)點(diǎn)，和前面滿二叉樹編號從1到12的節(jié)點(diǎn)位置完全對應(yīng)。因此這個樹是完全二叉樹。
完全二叉樹的條件沒有滿二叉樹那么苛刻：滿二叉樹要求所有分支都是滿的；而完全二叉樹只需保證最后一個節(jié)點(diǎn)之前的節(jié)點(diǎn)都齊全即可。
5.2二叉樹的存儲方式
二叉樹屬于邏輯結(jié)構(gòu)，它可以通過多種物理結(jié)構(gòu)來表達(dá)。
鏈?zhǔn)酱鎯?/strong>是二叉樹最直觀的存儲方式。二叉樹的每一個節(jié)點(diǎn)包含3部分。
存儲數(shù)據(jù)的data變量
指向左孩子的left指針
指向右孩子的right指針
使用數(shù)組存儲時，會按照層級順序把二叉樹的節(jié)點(diǎn)放到數(shù)組中對應(yīng)的位置上。如果某一個節(jié)點(diǎn)的左孩子或右孩子空缺，則數(shù)組的相應(yīng)位置也空出來。這樣可以更方便地在數(shù)組中定位二叉樹的孩子節(jié)點(diǎn)和父節(jié)點(diǎn)。
假設(shè)一個父節(jié)點(diǎn)的下標(biāo)是parent，那么它的左孩子節(jié)點(diǎn)下標(biāo)就是2×parent + 1；右孩子節(jié)點(diǎn)下標(biāo)就是2×parent + 2。
顯然，對于一個稀疏的二叉樹來說，用數(shù)組表示法是非常浪費(fèi)空間的。
什么樣的二叉樹最適合用數(shù)組表示呢？二叉堆這種特殊的完全二叉樹，就是用數(shù)組來存儲的。
5.3二叉查找樹
二叉樹包含許多特殊的形式，每一種形式都有自己的作用，但是其最主要的應(yīng)用還在于進(jìn)行查找操作和維持相對順序這兩個方面。
二叉查找樹在二叉樹的基礎(chǔ)上增加了以下幾個條件。
如果左子樹不為空，則左子樹上所有節(jié)點(diǎn)的值均小于根節(jié)點(diǎn)的值
如果右子樹不為空，則右子樹上所有節(jié)點(diǎn)的值均大于根節(jié)點(diǎn)的值
左、右子樹也都是二叉查找樹
下圖就是一個標(biāo)準(zhǔn)的二叉查找樹。
二叉查找樹的這些條件有什么用呢？當(dāng)然是為了查找方便。
對于一個節(jié)點(diǎn)分布相對均衡的二叉查找樹來說，如果節(jié)點(diǎn)總數(shù)是n，那么搜索節(jié)點(diǎn)的時間復(fù)雜度就是O(logn)，和樹的深度是一樣的。這種依靠比較大小來逐步查找的方式，和二分查找算法非常相似。
二叉查找樹要求左子樹小于父節(jié)點(diǎn)，右子樹大于父節(jié)點(diǎn)，正是這樣保證了二叉樹的有序性。
因此二叉查找樹還有另一個名字——二叉排序樹（binary sort tree）。
新插入的節(jié)點(diǎn)，同樣要遵循二叉排序樹的原則。
5.3.1二叉查找樹的自平衡問題：
在插入新元素的過程中會遇到問題，比如在二叉排序樹中依次插入9、8、7、6、5、4，可能會出現(xiàn)下面的結(jié)果。
這樣不只是外觀看起來變得怪異了，查詢節(jié)點(diǎn)的時間復(fù)雜度也退化成了O(n)。
解決這個問題就涉及到二叉樹的自平衡。二叉樹自平衡的方式有多種，如紅黑樹、AVL樹、樹堆等。
5.4二叉堆
二叉堆本質(zhì)上是一種完全二叉樹，它分為最大堆和最小堆。二叉堆雖然是一個完全二叉樹，但它的存儲方式并不是鏈?zhǔn)酱鎯Γ琼樞虼鎯?。換句話說，二叉堆的所有節(jié)點(diǎn)都存儲在數(shù)組中。
什么是最大堆呢？最大堆的任何一個父節(jié)點(diǎn)的值，都大于或等于它左、右孩子節(jié)點(diǎn)的值。
什么是最小堆呢？最小堆的任何一個父節(jié)點(diǎn)的值，都小于或等于它左、右孩子節(jié)點(diǎn)的值。
二叉堆的根節(jié)點(diǎn)叫作堆頂。
最大堆和最小堆的特點(diǎn)決定了：最大堆的堆頂是整個堆中的最大元素；最小堆的堆頂是整個堆中的最小元素。
對于二叉堆，有如下幾種操作。其中堆的插入和刪除操作的時間復(fù)雜度是O(logn)。但構(gòu)建堆的時間復(fù)雜度卻并不是O(nlogn)，而是O(n)。
插入節(jié)點(diǎn)。
刪除節(jié)點(diǎn)。
構(gòu)建二叉堆。
這幾種操作都基于堆的自我調(diào)整。所謂堆的自我調(diào)整，就是把一個不符合堆性質(zhì)的完全二叉樹，調(diào)整成一個堆。下面以最小堆為例，看看二叉堆是如何進(jìn)行自我調(diào)整的。
5.4.1插入節(jié)點(diǎn)
當(dāng)二叉堆插入節(jié)點(diǎn)時，插入位置是完全二叉樹的最后一個位置。例如插入一個新節(jié)點(diǎn)，值是 0。
這時，新節(jié)點(diǎn)的父節(jié)點(diǎn)5比0大，顯然不符合最小堆的性質(zhì)。于是讓新節(jié)點(diǎn)“上浮”，和父節(jié)點(diǎn)交換位置。
繼續(xù)用節(jié)點(diǎn)0和父節(jié)點(diǎn)3做比較，因?yàn)?小于3，則讓新節(jié)點(diǎn)繼續(xù)“上浮”。
繼續(xù)比較，最終新節(jié)點(diǎn)0“上浮”到了堆頂位置。
5.4.2刪除節(jié)點(diǎn)
二叉堆刪除節(jié)點(diǎn)的過程和插入節(jié)點(diǎn)的過程正好相反，所刪除的是處于堆頂?shù)墓?jié)點(diǎn)。例如刪除最小堆的堆頂節(jié)點(diǎn)1。
這時，為了繼續(xù)維持完全二叉樹的結(jié)構(gòu)，我們把堆的最后一個節(jié)點(diǎn)10臨時補(bǔ)到原本堆頂?shù)奈恢谩?/p>
接下來，讓暫處堆頂位置的節(jié)點(diǎn)10和它的左、右孩子進(jìn)行比較，如果左、右孩子節(jié)點(diǎn)中最小的一個（顯然是節(jié)點(diǎn)2）比節(jié)點(diǎn)10小，那么讓節(jié)點(diǎn)10“下沉”。
繼續(xù)讓節(jié)點(diǎn)10和它的左、右孩子做比較，左、右孩子中最小的是節(jié)點(diǎn)7，由于10大于7，讓節(jié)點(diǎn)10繼續(xù)“下沉”。
這樣一來，二叉堆重新得到了調(diào)整。
5.4.3構(gòu)建二叉堆
構(gòu)建二叉堆，也就是把一個無序的完全二叉樹調(diào)整為二叉堆，本質(zhì)就是讓所有非葉子節(jié)點(diǎn)依次“下沉”。
下面舉一個無序完全二叉樹的例子，如下圖所示。
首先，從最后一個非葉子節(jié)點(diǎn)開始，也就是從節(jié)點(diǎn)10開始。如果節(jié)點(diǎn)10大于它左、右孩子節(jié)點(diǎn)中最小的一個，則節(jié)點(diǎn)10“下沉”。
接下來輪到節(jié)點(diǎn)3，如果節(jié)點(diǎn)3大于它左、右孩子節(jié)點(diǎn)中最小的一個，則節(jié)點(diǎn)3“下沉”。
然后輪到節(jié)點(diǎn)1，如果節(jié)點(diǎn)1大于它左、右孩子節(jié)點(diǎn)中最小的一個，則節(jié)點(diǎn)1“下沉”。事實(shí)上節(jié)點(diǎn)1小于它的左、右孩子，所以不用改變。
接下來輪到節(jié)點(diǎn)7，如果節(jié)點(diǎn)7大于它左、右孩子節(jié)點(diǎn)中最小的一個，則節(jié)點(diǎn)7”下沉“。
節(jié)點(diǎn)7繼續(xù)比較，繼續(xù)“下沉”。
經(jīng)過上述幾輪比較和“下沉”操作，最終每一節(jié)點(diǎn)都小于它的左、右孩子節(jié)點(diǎn)，一個無序的完全二叉樹就被構(gòu)建成了一個最小堆。
5.5優(yōu)先隊(duì)列
優(yōu)先隊(duì)列不再遵循先入先出的原則，而是分為兩種情況。
最大優(yōu)先隊(duì)列，無論入隊(duì)順序如何，都是當(dāng)前最大的元素優(yōu)先出隊(duì)
最小優(yōu)先隊(duì)列，無論入隊(duì)順序如何，都是當(dāng)前最小的元素優(yōu)先出隊(duì)
要實(shí)現(xiàn)以上需求，利用線性數(shù)據(jù)結(jié)構(gòu)并非不能實(shí)現(xiàn)，但是時間復(fù)雜度較高。一般采用二叉堆來實(shí)現(xiàn)優(yōu)化隊(duì)列，可以用最大堆來實(shí)現(xiàn)最大優(yōu)先隊(duì)列，用最小堆 來實(shí)現(xiàn)最小優(yōu)化隊(duì)列，這樣的話，每一次入隊(duì)操作就是堆的插入操作，每一次出隊(duì)操作就是刪除堆頂節(jié)點(diǎn)。二叉堆節(jié)點(diǎn)“上浮”和“下沉”的時間復(fù)雜度都是O(logn)，所以優(yōu)先隊(duì)列入隊(duì)和出隊(duì)的時間復(fù)雜度也是O(logn)。
參考資料：《漫畫算法：小灰的算法之旅》
