1. 概念

隊列是一種先進(jìn)先出的結(jié)構(gòu)，但是有些時候，要操作的數(shù)據(jù)帶有優(yōu)先級，一般出隊時，優(yōu)先級較高的元素先出隊，這種數(shù)據(jù)結(jié)構(gòu)就叫做優(yōu)先級隊列。

比如：你在打音游的時候，你的朋友給你打了個電話，這種時候，就應(yīng)該優(yōu)先處理電話，然后再來繼續(xù)打音游，此時，電話就是優(yōu)先級較高的。

在這種情況下，數(shù)據(jù)結(jié)構(gòu)應(yīng)該提供兩個最基本的操作，一個是返回優(yōu)先級最高的對象，一個是添加新的對象。這種數(shù)據(jù)結(jié)構(gòu)就是優(yōu)先級隊列(Priority Queue)。

2. 無序數(shù)組實(shí)現(xiàn)

要點(diǎn)

1. 入隊保持順序
2. 出隊前找到優(yōu)先級最高的出隊，相當(dāng)于一次選擇排序

隊列實(shí)現(xiàn)類：

package com.itheima.datastructure.priorityqueue;import com.itheima.datastructure.queue.Queue;/*** 優(yōu)先隊列實(shí)現(xiàn)類，基于無序數(shù)組。* 使用無序數(shù)組實(shí)現(xiàn)優(yōu)先隊列，隊列中的元素必須實(shí)現(xiàn)Priority接口，以提供優(yōu)先級比較的方法。* 該實(shí)現(xiàn)類提供了標(biāo)準(zhǔn)的隊列操作，包括入隊、出隊、查看隊首元素、判斷隊列為空或滿等。** @param <E> 隊列元素類型，必須實(shí)現(xiàn)Priority接口。*/
@SuppressWarnings("all")
public class PriorityQueue1<E extends Priority> implements Queue<E> {// 存儲隊列元素的數(shù)組，元素類型為Priority接口的實(shí)現(xiàn)類。Priority[] array;// 當(dāng)前隊列的大小。int size;/*** 構(gòu)造函數(shù)，初始化優(yōu)先隊列。* * @param capacity 隊列的容量，即最大元素數(shù)量。*/public PriorityQueue1(int capacity) {array = new Priority[capacity];}/*** 入隊操作，將元素添加到隊列尾部。* * @param e 待添加到隊列的元素，必須實(shí)現(xiàn)Priority接口。* @return 添加成功返回true，隊列已滿返回false。*/@Override // O(1)public boolean offer(E e) {if (isFull()) {return false;}array[size++] = e;return true;}/*** 查找優(yōu)先級最高的元素的索引。* * @return 優(yōu)先級最高的元素的索引。*/// 返回優(yōu)先級最高的索引值private int selectMax() {int max = 0;for (int i = 1; i < size; i++) {if (array[i].priority() > array[max].priority()) {max = i;}}return max;}/*** 出隊操作，移除并返回優(yōu)先級最高的元素。* * @return 被移除的優(yōu)先級最高的元素，隊列為空時返回null。*/@Override // O(n)public E poll() {if (isEmpty()) {return null;}int max = selectMax();E e = (E) array[max];remove(max);return e;}/*** 從數(shù)組中移除指定索引的元素，并將后續(xù)元素向前移動一位。* * @param index 待移除元素的索引。*/private void remove(int index) {if (index < size - 1) {// 移動System.arraycopy(array, index + 1,array, index, size - 1 - index);}array[--size] = null; // help GC}/*** 查看隊首元素，即優(yōu)先級最高的元素，但不移除。* * @return 隊首元素，隊列為空時返回null。*/@Overridepublic E peek() {if (isEmpty()) {return null;}int max = selectMax();return (E) array[max];}/*** 判斷隊列是否為空。* * @return 隊列為空返回true，否則返回false。*/@Overridepublic boolean isEmpty() {return size == 0;}/*** 判斷隊列是否已滿。* * @return 隊列已滿返回true，否則返回false。*/@Overridepublic boolean isFull() {return size == array.length;}
}

優(yōu)先級類：

package com.itheima.datastructure.priorityqueue;public interface Priority {/*** 返回對象的優(yōu)先級, 約定數(shù)字越大, 優(yōu)先級越高* @return 優(yōu)先級*/int priority();
}

條目類：

/*** 優(yōu)先隊列中的條目類，實(shí)現(xiàn)了Priority接口。* 該類用于存儲具有特定優(yōu)先級的值。*/
package com.itheima.datastructure.priorityqueue;class Entry implements Priority {String value; // 條目的值int priority; // 條目的優(yōu)先級/*** 構(gòu)造函數(shù)，創(chuàng)建一個具有指定優(yōu)先級的條目。* @param priority 條目的優(yōu)先級*/public Entry(int priority) {this.priority = priority;}/*** 構(gòu)造函數(shù)，創(chuàng)建一個具有指定值和優(yōu)先級的條目。* @param value 條目的值* @param priority 條目的優(yōu)先級*/public Entry(String value, int priority) {this.value = value;this.priority = priority;}/*** 返回條目的優(yōu)先級。* @return 條目的優(yōu)先級*/@Overridepublic int priority() {return priority;}/*** 返回表示條目的字符串，格式為"(值 priority=優(yōu)先級)"。* @return 表示條目的字符串*/@Overridepublic String toString() {return "(" + value + " priority=" + priority + ")";}/*** 比較當(dāng)前對象與另一個對象是否相等。* 兩個條目相等的定義是它們的優(yōu)先級相同。* @param o 要比較的對象* @return 如果兩個對象的優(yōu)先級相同，則返回true；否則返回false。*/@Overridepublic boolean equals(Object o) {if (this == o) return true;if (o == null || getClass() != o.getClass()) return false;Entry entry = (Entry) o;return priority == entry.priority;}/*** 計算當(dāng)前對象的哈希碼，基于條目的優(yōu)先級。* @return 當(dāng)前對象的哈希碼*/@Overridepublic int hashCode() {return priority;}
}

測試類：

package com.itheima.datastructure.priorityqueue;import org.junit.jupiter.api.Test;import java.util.Arrays;import static org.junit.jupiter.api.Assertions.assertEquals;
import static org.junit.jupiter.api.Assertions.assertFalse;/*優(yōu)先級隊列       一端進(jìn), 另一端出       按優(yōu)先級出隊普通隊列        一端進(jìn), 另一端出       FIFO
*/
public class TestPriorityQueue1 {@Testpublic void poll() {PriorityQueue1<Entry> queue = new PriorityQueue1<>(5);queue.offer(new Entry("task1", 4));queue.offer(new Entry("task2", 3));queue.offer(new Entry("task3", 2));queue.offer(new Entry("task4", 5));queue.offer(new Entry("task5", 1));assertFalse(queue.offer(new Entry("task6", 7)));System.out.println(Arrays.toString(queue.array));assertEquals(5, queue.poll().priority());System.out.println(Arrays.toString(queue.array));assertEquals(4, queue.poll().priority());assertEquals(3, queue.poll().priority());assertEquals(2, queue.poll().priority());assertEquals(1, queue.poll().priority());}
}

測試結(jié)果：

[(task1 priority=4), (task2 priority=3), (task3 priority=2), (task4 priority=5), (task5 priority=1)]
[(task1 priority=4), (task2 priority=3), (task3 priority=2), (task5 priority=1), null]

3. 有序數(shù)組實(shí)現(xiàn)

要點(diǎn)

1. 入隊后排好序，優(yōu)先級最高的排列在尾部
2. 出隊只需刪除尾部元素即可

隊列實(shí)現(xiàn)類：

package com.itheima.datastructure.priorityqueue;import com.itheima.datastructure.queue.Queue;/*** 基于有序數(shù)組實(shí)現(xiàn)的優(yōu)先隊列。* 使用優(yōu)先級高的元素先出（FIFO）的策略。** @param <E> 隊列中元素的類型，必須實(shí)現(xiàn)Priority接口以定義優(yōu)先級。*/
@SuppressWarnings("all")
public class PriorityQueue2<E extends Priority> implements Queue<E> {// 存儲元素的數(shù)組，數(shù)組中的元素必須實(shí)現(xiàn)Priority接口Priority[] array;// 當(dāng)前隊列中元素的數(shù)量int size;/*** 構(gòu)造函數(shù)，初始化優(yōu)先隊列。** @param capacity 隊列的容量，即最大元素數(shù)量。*/public PriorityQueue2(int capacity) {array = new Priority[capacity];}/*** 向隊列中添加一個元素。* 如果隊列已滿，則返回false。** @param e 要添加到隊列的元素，必須實(shí)現(xiàn)Priority接口。* @return 如果添加成功，返回true；否則返回false。*/@Overridepublic boolean offer(E e) {if (isFull()) {return false;}insert(e);size++;return true;}/*** 將元素插入到隊列的正確位置，以保持隊列的有序性。** @param e 要插入的元素。*/// O(n)private void insert(E e) {int i = size - 1;while (i >= 0 && array[i].priority() > e.priority()) {array[i + 1] = array[i];i--;}array[i + 1] = e;}/*** 從隊列中移除并返回優(yōu)先級最高的元素。* 如果隊列為空，則返回null。** @return 被移除的元素，如果隊列為空，則返回null。*/// O(1)@Overridepublic E poll() {if (isEmpty()) {return null;}E e = (E) array[size - 1];array[--size] = null; // help GCreturn e;}/*** 返回優(yōu)先級最高的元素，但不移除它。* 如果隊列為空，則返回null。** @return 隊列頭部的元素，如果隊列為空，則返回null。*/@Overridepublic E peek() {if (isEmpty()) {return null;}return (E) array[size - 1];}/*** 檢查隊列是否為空。** @return 如果隊列為空，返回true；否則返回false。*/@Overridepublic boolean isEmpty() {return size == 0;}/*** 檢查隊列是否已滿。** @return 如果隊列已滿，返回true；否則返回false。*/@Overridepublic boolean isFull() {return size == array.length;}
}

測試類：

package com.itheima.datastructure.priorityqueue;import org.junit.jupiter.api.Test;import static org.junit.jupiter.api.Assertions.assertEquals;
import static org.junit.jupiter.api.Assertions.assertFalse;public class TestPriorityQueue2 {@Testpublic void poll() {PriorityQueue2<Entry> queue = new PriorityQueue2<>(5);queue.offer(new Entry("task1", 4));queue.offer(new Entry("task2", 3));queue.offer(new Entry("task3", 2));queue.offer(new Entry("task4", 5));queue.offer(new Entry("task5", 1));assertFalse(queue.offer(new Entry("task6", 7)));assertEquals("task4", queue.peek().value);assertEquals("task4", queue.poll().value);assertEquals("task1", queue.poll().value);assertEquals("task2", queue.poll().value);assertEquals("task3", queue.poll().value);assertEquals("task5", queue.poll().value);}
}

4. 堆實(shí)現(xiàn)

JDK1.8中的 PriorityQueue 底層使用了堆這種數(shù)據(jù)結(jié)構(gòu)，而堆實(shí)際就是在完全二叉樹的基礎(chǔ)上進(jìn)行了一些調(diào)整。也就是說，堆的是由完全二叉樹調(diào)整而來的，可以存儲到數(shù)組中。

堆的概念
如果有一個關(guān)鍵碼的集合K = {k0，k1， k2，…，kn-1}，把它的所有元素按完全二叉樹的順序存儲方式存儲在一個一維數(shù)組中，并滿足：Ki <= K2i+1 且 Ki<= K2i+2 (Ki >= K2i+1 且 Ki >= K2i+2) i = 0，1，2…，則稱為 小堆(或 大堆)。將根節(jié)點(diǎn)最大的堆叫做最大堆或大根堆，根節(jié)點(diǎn)最小的堆叫做最小堆或小根堆。

堆的性質(zhì)：

• 堆中某個節(jié)點(diǎn)的值總是不大于或不小于其父節(jié)點(diǎn)的值。
• 堆總是一棵完全二叉樹。
  如圖：
  
  

計算機(jī)科學(xué)中，堆是一種基于樹的數(shù)據(jù)結(jié)構(gòu)，通常用完全二叉樹實(shí)現(xiàn)。堆的特性如下

• 在大頂堆中，任意節(jié)點(diǎn) C 與它的父節(jié)點(diǎn) P 符合 $P.value\ge C.value$
• 而小頂堆中，任意節(jié)點(diǎn) C 與它的父節(jié)點(diǎn) P 符合 $P.value\le C.value$
• 最頂層的節(jié)點(diǎn)（沒有父親）稱之為 root 根節(jié)點(diǎn)

完全二叉樹可以使用數(shù)組來表示

特征

● 如果從索引 0 開始存儲節(jié)點(diǎn)數(shù)據(jù)
○ 節(jié)點(diǎn) $i$ 的父節(jié)點(diǎn)為 $floor((i?1)/2)$，當(dāng) $i>0$ 時
○ 節(jié)點(diǎn) $i$ 的左子節(jié)點(diǎn)為 $2i+1$，右子節(jié)點(diǎn)為 $2i+2$，當(dāng)然它們得 $<size$
● 如果從索引 1 開始存儲節(jié)點(diǎn)數(shù)據(jù)
○ 節(jié)點(diǎn) $i$ 的父節(jié)點(diǎn)為 $floor(i/2)$，當(dāng) $i>1$ 時
○ 節(jié)點(diǎn) $i$ 的左子節(jié)點(diǎn)為 $2i$，右子節(jié)點(diǎn)為 $2i+1$，同樣得 $<size$

實(shí)現(xiàn)類：

package com.itheima.datastructure.priorityqueue;import com.itheima.datastructure.queue.Queue;/*** 基于大頂堆實(shí)現(xiàn)的優(yōu)先隊列。* 大頂堆是一個完全二叉樹，每個父節(jié)點(diǎn)的優(yōu)先級不小于其子節(jié)點(diǎn)的優(yōu)先級。* @param <E> 隊列中元素的類型，必須實(shí)現(xiàn)Priority接口以定義元素的優(yōu)先級。*/
@SuppressWarnings("all")
public class PriorityQueue4<E extends Priority> implements Queue<E> {Priority[] array; // 存儲優(yōu)先隊列元素的數(shù)組int size; // 當(dāng)前隊列的大小/*** 構(gòu)造函數(shù)，初始化優(yōu)先隊列。* @param capacity 隊列的初始容量。*/public PriorityQueue4(int capacity) {array = new Priority[capacity];}/*** 向隊列中添加一個元素。* 如果隊列已滿，則返回false；否則將元素加入隊列，并調(diào)整堆以保持大頂堆的性質(zhì)。* @param offered 要添加到隊列的元素。* @return 如果添加成功，返回true；如果隊列已滿，返回false。*//*1. 入堆新元素, 加入到數(shù)組末尾 (索引位置 child)2. 不斷比較新加元素與它父節(jié)點(diǎn)(parent)優(yōu)先級 (上浮)- 如果父節(jié)點(diǎn)優(yōu)先級低, 則向下移動, 并找到下一個 parent- 直至父節(jié)點(diǎn)優(yōu)先級更高或 child==0 為止*/@Overridepublic boolean offer(E offered) {// 檢查隊列是否已滿，如果已滿，則拒絕添加新元素并返回false。if (isFull()) {return false;}// 將新元素插入到數(shù)組的末尾，并記錄其位置。int child = size++;// 計算新元素的父節(jié)點(diǎn)位置。int parent = (child - 1) / 2;// 上浮新元素，直到它位于正確的位置或者它是根元素。while (child > 0 && offered.priority() > array[parent].priority()) {// 將當(dāng)前元素的父元素移動到當(dāng)前元素的位置，準(zhǔn)備繼續(xù)上浮。array[child] = array[parent];child = parent;// 更新當(dāng)前元素的父節(jié)點(diǎn)位置。parent = (child - 1) / 2;}// 將新元素放置在最終的位置上，完成添加。array[child] = offered;// 添加成功，返回true。return true;}/*** 從隊列中移除并返回優(yōu)先級最高的元素（即堆頂元素）。* 如果隊列為空，則返回null。* @return 優(yōu)先級最高的元素，如果隊列為空，則返回null。*//*1. 交換堆頂和尾部元素, 讓尾部元素出隊2. (下潛)- 從堆頂開始, 將父元素與兩個孩子較大者交換- 直到父元素大于兩個孩子, 或沒有孩子為止*/@Overridepublic E poll() {// 檢查隊列是否為空，如果為空則返回nullif (isEmpty()) {return null;}// 交換堆頂元素（優(yōu)先級最高）和隊列尾部元素，準(zhǔn)備移除堆頂元素swap(0, size - 1);// 更新隊列大小，表示已移除一個元素size--;// 獲取并保存即將返回的堆頂元素Priority e = array[size];// 將隊列尾部元素置為null，幫助垃圾回收array[size] = null; // help GC// 調(diào)整堆結(jié)構(gòu)，確保堆的性質(zhì)依然滿足// 下潛down(0);// 返回移除的堆頂元素return (E) e;}/*** 將元素向下調(diào)整以保持大頂堆的性質(zhì)。* 此方法假設(shè)調(diào)用時堆已經(jīng)部分有序，它通過比較父節(jié)點(diǎn)和其子節(jié)點(diǎn)的優(yōu)先級來確保整個堆仍然滿足大頂堆的定義。* 如果父節(jié)點(diǎn)的優(yōu)先級低于某個子節(jié)點(diǎn)，則交換它們，并繼續(xù)向下調(diào)整子節(jié)點(diǎn)，直到整個子樹滿足大頂堆的條件。** @param parent 需要向下調(diào)整的父節(jié)點(diǎn)的索引。*//*** 將元素向下調(diào)整以保持大頂堆的性質(zhì)。* @param parent 需要向下調(diào)整的元素的索引。*/private void down(int parent) {// 計算左子節(jié)點(diǎn)和右子節(jié)點(diǎn)的索引int left = 2 * parent + 1;int right = left + 1;// 假設(shè)當(dāng)前父節(jié)點(diǎn)的優(yōu)先級最高int max = parent; // 假設(shè)父元素優(yōu)先級最高// 如果左子節(jié)點(diǎn)存在且優(yōu)先級高于當(dāng)前最大值，則更新最大值索引if (left < size && array[left].priority() > array[max].priority()) {max = left;}// 如果右子節(jié)點(diǎn)存在且優(yōu)先級高于當(dāng)前最大值，則更新最大值索引if (right < size && array[right].priority() > array[max].priority()) {max = right;}// 如果最大值不是初始的父節(jié)點(diǎn)，則交換它們，并遞歸向下調(diào)整新父節(jié)點(diǎn)if (max != parent) { // 有孩子比父親大swap(max, parent);down(max);}}/*** 交換數(shù)組中兩個元素的位置。* @param i 第一個元素的索引。* @param j 第二個元素的索引。*/private void swap(int i, int j) {Priority t = array[i];array[i] = array[j];array[j] = t;}/*** 返回隊列中優(yōu)先級最高的元素（即堆頂元素），但不移除它。* 如果隊列為空，則返回null。* @return 優(yōu)先級最高的元素，如果隊列為空，則返回null。*/@Overridepublic E peek() {if (isEmpty()) {return null;}return (E) array[0];}/*** 檢查隊列是否為空。* @return 如果隊列為空，返回true；否則返回false。*/@Overridepublic boolean isEmpty() {return size == 0;}/*** 檢查隊列是否已滿。* @return 如果隊列已滿，返回true；否則返回false。*/@Overridepublic boolean isFull() {return size == array.length;}
}

5. 習(xí)題

E01. 合并多個有序鏈表-Leetcode 23

給你一個鏈表數(shù)組，每個鏈表都已經(jīng)按升序排列。

請你將所有鏈表合并到一個升序鏈表中，返回合并后的鏈表。

示例 1：

輸入：lists = [[1,4,5],[1,3,4],[2,6]]
輸出：[1,1,2,3,4,4,5,6]
解釋：鏈表數(shù)組如下：
[1->4->5,1->3->4,2->6
]
將它們合并到一個有序鏈表中得到。
1->1->2->3->4->4->5->6

示例 2：

輸入：lists = []
輸出：[]
示例 3：輸入：lists = [[]]
輸出：[]

提示：

k == lists.length
0 <= k <= 10^4
0 <= lists[i].length <= 500
-10^4 <= lists[i][j] <= 10^4
lists[i] 按 升序 排列
lists[i].length 的總和不超過 10^4

這道題目之前解答過，現(xiàn)在用剛學(xué)的優(yōu)先級隊列來實(shí)現(xiàn)一下
題目中要從小到大排列，因此選擇用小頂堆來實(shí)現(xiàn)，思路如下圖：

自定義小頂堆如下

package com.itheima.datastructure.priorityqueue;import com.itheima.datastructure.linkedlist.ListNode;/*** 小頂堆類，實(shí)現(xiàn)優(yōu)先隊列功能。* 小頂堆是一個完全二叉樹，每個父節(jié)點(diǎn)的值都小于或等于其子節(jié)點(diǎn)的值。*/
/*** <b>小頂堆</b>*/
public class MinHeap {/*** 堆數(shù)組，存儲堆中的節(jié)點(diǎn)。*/ListNode[] array;/*** 堆的當(dāng)前大小，即堆中節(jié)點(diǎn)的數(shù)量。*/int size;/*** 構(gòu)造函數(shù)，初始化小頂堆。** @param capacity 堆的容量，即堆數(shù)組的大小。*/public MinHeap(int capacity) {array = new ListNode[capacity];}/*** 將一個節(jié)點(diǎn)添加到最小堆中。* 如果堆已滿，則拒絕添加，并返回false；否則，將節(jié)點(diǎn)添加到堆中并維護(hù)堆的性質(zhì)。** @param offered 要添加到堆中的節(jié)點(diǎn)。* @return 如果成功添加節(jié)點(diǎn)，則返回true；如果堆已滿，則返回false。*//*** 向堆中插入一個節(jié)點(diǎn)。** @param offered 要插入的節(jié)點(diǎn)。* @return 如果堆已滿，返回false；否則返回true。*/public boolean offer(ListNode offered) {// 檢查堆是否已滿，如果已滿則無法添加新節(jié)點(diǎn)if (isFull()) {return false;}// 將新節(jié)點(diǎn)插入到堆的最后一個位置，并更新堆的大小int child = size++;// 計算新節(jié)點(diǎn)的父節(jié)點(diǎn)位置int parent = (child - 1) / 2;// 當(dāng)節(jié)點(diǎn)不在根位置且小于其父節(jié)點(diǎn)時，向上調(diào)整節(jié)點(diǎn)位置以維護(hù)最小堆性質(zhì)while (child > 0 && offered.val < array[parent].val) {// 將父節(jié)點(diǎn)值復(fù)制到當(dāng)前節(jié)點(diǎn)array[child] = array[parent];// 更新當(dāng)前節(jié)點(diǎn)為父節(jié)點(diǎn)，并計算新的父節(jié)點(diǎn)位置child = parent;parent = (child - 1) / 2;}// 將新節(jié)點(diǎn)值插入到最終位置，完成添加array[child] = offered;return true;}/*** 從堆中移除并返回最小的節(jié)點(diǎn)。** @return 如果堆為空，返回null；否則返回移除的最小節(jié)點(diǎn)。*/public ListNode poll() {if (isEmpty()) {return null;}swap(0, size - 1);size--;ListNode e = array[size];array[size] = null; // help GC// 下潛down(0);return e;}/*** 將堆中指定元素下沉以維護(hù)堆的性質(zhì)。* 這個方法是堆排序或優(yōu)先隊列操作中的關(guān)鍵部分，它確保堆的性質(zhì)得以維持。* 當(dāng)插入一個新元素或某個元素的值被更新后，可能需要調(diào)用此方法來重新調(diào)整堆。** @param parent 要下沉的元素的索引，該元素是其子節(jié)點(diǎn)的父節(jié)點(diǎn)。*/private void down(int parent) {// 計算左子節(jié)點(diǎn)和右子節(jié)點(diǎn)的索引int left = 2 * parent + 1;int right = left + 1;// 假設(shè)當(dāng)前父節(jié)點(diǎn)是最小的// 如果左子節(jié)點(diǎn)存在且值小于當(dāng)前最小值，則更新最小值為左子節(jié)點(diǎn)int min = parent; // 假設(shè)父元素最小if (left < size && array[left].val < array[min].val) {min = left;}// 如果右子節(jié)點(diǎn)存在且值小于當(dāng)前最小值，則更新最小值為右子節(jié)點(diǎn)if (right < size && array[right].val < array[min].val) {min = right;}// 如果找到的最小值不是初始的父節(jié)點(diǎn)，則交換它們并繼續(xù)下沉最小值節(jié)點(diǎn)if (min != parent) { // 有孩子比父親小swap(min, parent);down(min);}}/*** 交換堆數(shù)組中兩個節(jié)點(diǎn)的位置。** @param i 第一個節(jié)點(diǎn)的索引。* @param j 第二個節(jié)點(diǎn)的索引。*/private void swap(int i, int j) {ListNode t = array[i];array[i] = array[j];array[j] = t;}/*** 檢查堆是否為空。** @return 如果堆為空，返回true；否則返回false。*/public boolean isEmpty() {return size == 0;}/*** 檢查堆是否已滿。** @return 如果堆已滿，返回true；否則返回false。*/public boolean isFull() {return size == array.length;}
}

代碼

package com.itheima.datastructure.priorityqueue;import com.itheima.datastructure.linkedlist.ListNode;/*** 合并多個有序鏈表的工具類。*/
public class E01Leetcode23 {/*** 使用最小堆合并多個有序鏈表。* * @param lists 多個有序鏈表的數(shù)組形式。* @return 合并后的單個有序鏈表。*/public ListNode mergeKLists2(ListNode[] lists) {MinHeap heap = new MinHeap(100);// 將所有鏈表的節(jié)點(diǎn)加入最小堆// 1. 將鏈表的所有節(jié)點(diǎn)加入小頂堆for (ListNode p : lists) {while (p != null) {heap.offer(p);p = p.next;}}// 從最小堆中依次取出節(jié)點(diǎn)構(gòu)建合并后的鏈表// 2. 不斷從堆頂移除最小元素, 加入新鏈表ListNode s = new ListNode(-1, null);ListNode t = s;while(!heap.isEmpty()) {ListNode min = heap.poll();t.next = min;t = min;t.next = null; // 保證尾部節(jié)點(diǎn)指向 null}return s.next;}/*** 使用最小堆合并多個有序鏈表的另一種實(shí)現(xiàn)方式。* * @param lists 多個有序鏈表的數(shù)組形式。* @return 合并后的單個有序鏈表。*/public ListNode mergeKLists(ListNode[] lists) {MinHeap heap = new MinHeap(lists.length);// 將所有鏈表的頭節(jié)點(diǎn)加入最小堆// 1. 將鏈表的頭節(jié)點(diǎn)加入小頂堆for (ListNode h : lists) {if(h != null) {heap.offer(h);}}// 從最小堆中依次取出節(jié)點(diǎn)構(gòu)建合并后的鏈表// 2. 不斷從堆頂移除最小元素, 加入新鏈表ListNode s = new ListNode(-1, null);ListNode t = s;while(!heap.isEmpty()) {ListNode min = heap.poll();t.next = min;t = min;// 將當(dāng)前節(jié)點(diǎn)的下一個節(jié)點(diǎn)加入最小堆// 將最小元素的下一個節(jié)點(diǎn)加入到堆if(min.next != null) {heap.offer(min.next);}}return s.next;}/*** 測試合并多個有序鏈表的函數(shù)。* * @param args 命令行參數(shù)。*/public static void main(String[] args) {ListNode[] lists = {ListNode.of(1, 4, 5),ListNode.of(1, 3, 4),ListNode.of(2, 6),null,};ListNode m = new E01Leetcode23().mergeKLists2(lists);System.out.println(m);}
}