2023學(xué)年完整公開課版PriorityQueue實(shí)現(xiàn)類

PriorityQueue實(shí)現(xiàn)類目錄Part01教學(xué)目標(biāo)Part02教學(xué)內(nèi)容Part04鞏固提高ContentsPart03教學(xué)總結(jié)Part01教學(xué)目標(biāo)教學(xué)目標(biāo)知識(shí)目標(biāo)PriorityQueue類的使用01能力目標(biāo)掌握PriorityQueue類的使用02Part02教學(xué)內(nèi)容1.Queue接口java.util

接口Queue<E>類型參數(shù)：E-集合中所保存元素的類型。所有父接口：Collection<E>,Iterable<E>所有已知子接口：BlockingQueue<E>所有已知實(shí)現(xiàn)類：AbstractQueue,ArrayBlockingQueue,ConcurrentLinkedQueue,DelayQueue,LinkedBlockingQueue,LinkedList,PriorityBlockingQueue,PriorityQueue,SynchronousQueue

2.PriorityQueue實(shí)現(xiàn)類PriorityQueue是一個(gè)比較標(biāo)準(zhǔn)的隊(duì)列實(shí)現(xiàn)類，之所以說它是比較標(biāo)準(zhǔn)的隊(duì)列實(shí)現(xiàn)，而不是絕對(duì)標(biāo)準(zhǔn)的隊(duì)列實(shí)現(xiàn)是因?yàn)椋篜riorityQueue保存隊(duì)列元素的順序并不是按加入隊(duì)列的順序，而是按隊(duì)列元素的大小進(jìn)行重新排序。因此當(dāng)調(diào)用peek方法或者poll方法來取出隊(duì)列中的元素時(shí)，并不是取出最先進(jìn)入隊(duì)列的元素是，而是取出隊(duì)列中最小的元素。如果不提供Comparator的話，優(yōu)先隊(duì)列中元素默認(rèn)按自然順序排列，也就是數(shù)字默認(rèn)是小的在隊(duì)列頭，字符串則按字典序排列。3.PriorityQueue的特點(diǎn)時(shí)間復(fù)雜度：remove()方法和add()方法時(shí)間復(fù)雜度為O(logn)，remove(Objectobj)和contains()方法需要O(n)時(shí)間復(fù)雜度，取隊(duì)頭則需要O(1)時(shí)間在初始化階段會(huì)執(zhí)行建堆函數(shù)，最終建立的是最小堆，每次出隊(duì)和入隊(duì)操作不能保證隊(duì)列元素的有序性，只能保證隊(duì)頭元素和新插入元素的有序性，如果需要有序輸出隊(duì)列中的元素，則只要調(diào)用Arrays.sort()方法即可可以使用Iterator的迭代器方法輸出隊(duì)列中元素PriorityQueue是非同步的，要實(shí)現(xiàn)同步需要調(diào)用java.util.concurrent包下的PriorityBlockingQueue類來實(shí)現(xiàn)同步在隊(duì)列中不允許使用null元素4.PriorityQueue構(gòu)造方法PriorityQueue()

使用默認(rèn)的初始容量（11）創(chuàng)建一個(gè)PriorityQueue，并根據(jù)其自然順序來排序其元素（使用Comparable）。PriorityQueue(intinitialCapacity)

使用指定的初始容量創(chuàng)建一個(gè)PriorityQueue，并根據(jù)其自然順序來排序其元素（使用Comparable）。PriorityQueue(intinitialCapacity,Comparator

comparator)

使用指定的初始容量創(chuàng)建一個(gè)PriorityQueue，并根據(jù)指定的比較器comparator來排序其元素。5.PriorityQueue常用方法add()和offer()add(Ee)和offer(Ee)的語義相同，都是向優(yōu)先隊(duì)列中插入元素，只是Queue接口規(guī)定二者對(duì)插入失敗時(shí)的處理不同，前者在插入失敗時(shí)拋出異常，后則則會(huì)返回false。對(duì)于PriorityQueue這兩個(gè)方法其實(shí)沒什么差別。element()和peek()element()和peek()的語義完全相同，都是獲取但不刪除隊(duì)首元素，也就是隊(duì)列中權(quán)值最小的那個(gè)元素，二者唯一的區(qū)別是當(dāng)方法失敗時(shí)前者拋出異常，后者返回null。根據(jù)小頂堆的性質(zhì)，堆頂那個(gè)元素就是全局最小的那個(gè)；由于堆用數(shù)組表示，根據(jù)下標(biāo)關(guān)系，0下標(biāo)處的那個(gè)元素既是堆頂元素。所以直接返回?cái)?shù)組0下標(biāo)處的那個(gè)元素即可。remove()和poll()remove()和poll()方法的語義也完全相同，都是獲取并刪除隊(duì)首元素，區(qū)別是當(dāng)方法失敗時(shí)前者拋出異常，后者返回null。由于刪除操作會(huì)改變隊(duì)列的結(jié)構(gòu)，為維護(hù)小頂堆的性質(zhì)，需要進(jìn)行必要的調(diào)整。remove(Objecto)remove(Objecto)方法用于刪除隊(duì)列中跟o相等的某一個(gè)元素（如果有多個(gè)相等，只刪除一個(gè)），該方法不是Queue接口內(nèi)的方法，而是Collection接口的方法。由于刪除操作會(huì)改變隊(duì)列結(jié)構(gòu)，所以要進(jìn)行調(diào)整；又由于刪除元素的位置可能是任意的，所以調(diào)整過程比其它函數(shù)稍加繁瑣。具體來說，remove(Objecto)可以分為2種情況：1.刪除的是最后一個(gè)元素。直接刪除即可，不需要調(diào)整。2.刪除的不是最后一個(gè)元素，從刪除點(diǎn)開始以最后一個(gè)元素為參照調(diào)用一次siftDown()即可。Part03教學(xué)總結(jié)教學(xué)總結(jié)1.Pr