關(guān)注微信公眾號：怒碼少年。
回復關(guān)鍵詞：【電子書】，領(lǐng)取多本計算機相關(guān)電子書

大家好，我是怒碼少年小碼。

今天開始進入新的篇章——堆！這里我默認了大家都知道堆的基本知識了，我們來看看關(guān)于堆的兩道高頻算法題吧。

數(shù)組中的第K個最大元素

LeetCode 215：給定整數(shù)數(shù)組 nums 和整數(shù) k，請返回數(shù)組中第 k 個最大的元素。

示例:

• 輸入: [3,2,1,5,6,4], k = 2
• 輸出: 5

分析：本題的方法有三種：選擇法、快速排序和堆查找

1. 選擇法

類似于冒泡排序，第一個排序找出第1大的元素，第二次排序找出第2大的元素，第k次排序找出第k大的元素。

2. 快速排序：之前已經(jīng)講過
3. 堆查找

利用堆解決這個問題：首先思考用最大堆還是最小堆？答：最小堆。

原因：構(gòu)造一個k大小的最小堆，則這個堆里存放的就是前k大的元素，只有比堆頂這個堆中最小的元素大，才能進入堆中。最后這個堆頂就是第k大的元素。

記憶口訣：

• 查找：找大用小，大的進；找小用大，小的進
• 排序：升序用小，降序用大。

以[3，2，3，1，2，4，5，1，5，6，2，3]，k=4。為例。注意：只有當前遍歷的元素，大于堆頂元素才會入堆，否則丟棄。

堆的代碼純手寫會很復雜，在Java中可以使用優(yōu)先隊列實現(xiàn)。

在 Java 中，PriorityQueue 是一個實現(xiàn)了優(yōu)先隊列（Priority Queue）的類。是基于優(yōu)先級的隊列，元素按照一定的優(yōu)先級順序進行排序并存儲。

 public int findKthLargest(int[] nums, int k) {//利用優(yōu)先隊列和最小堆完成if(k > nums.length){return -1;}int len = nums.length;//創(chuàng)建一個還有k個元素大小的最小堆PriorityQueue<Integer> minHeap = new PriorityQueue<>(k,(a,b)->a-b);for(int i =0 ; i<k ; i++){minHeap.add(nums[i]);}for(int i = k ; i <len ; i++){//獲取，但是不拿出，因為還不確定是不是要換Integer topEle = minHeap.peek();//只要當前遍歷的元素比堆頂元素大，堆頂彈出，當前遍歷的放進去if(nums[i] > topEle){minHeap.poll();minHeap.offer(nums[i]);}}return minHeap.peek();
}

offer()方法的作用是將元素插入到優(yōu)先隊列中，并根據(jù)定義的優(yōu)先級順序進行排序，以便在后續(xù)的操作中能夠按照優(yōu)先級順序提取元素。

合并 K 個升序鏈表

LeetCode 23：給你一個鏈表數(shù)組，每個鏈表都已經(jīng)按升序排列。請你將所有鏈表合并到一個升序鏈表中，返回合并后的鏈表。

示例：

• 輸入：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

分析：每個隊列都是從小到大排序的，每次都要找最小的元素，我們要用小頂堆，不同的是每次比較誰更小

堆合并的策略：不管幾個鏈表，最終都是按照順序來的。每次都將剩余節(jié)點的最小值加到輸出鏈表尾部，然后進行堆調(diào)整，最后堆空的時候，合并完成。

public ListNode mergeKLists(ListNode[] lists) {if(lists == null || lists.length == 0) return null;
//創(chuàng)建優(yōu)先隊列PriorityQueue<ListNode> q = new PriorityQueue<>(Comparator.comparing(node -> node.val));for(int i =0;i<lists.length;i++){if(lists[i] != null){q.add(lists[i]);}}ListNode dummy = new ListNode(0);ListNode tail = dummy;while(!q.isEmpty()){tail.next = q.poll();tail = tail.next;if(tail.next != null){q.add(tail.next);}}return dummy.next;
}

PriorityQueue<ListNode> q = new PriorityQueue<>(Comparator.comparing(node -> node.val)) 這段代碼的意思是創(chuàng)建了一個優(yōu)先隊列 q，并指定了節(jié)點的比較方式。

首先，使node -> node.val 是一個 Lambda 表達式，用于定義優(yōu)先隊列 q 的比較器。它表示一個匿名函數(shù)，接受 ListNode 類型的參數(shù) node，并返回 node.val。

具體來說，node -> node.val 表達式的作用是根據(jù)鏈表節(jié)點的值 val 進行比較。當兩個鏈表節(jié)點進行比較時，比較器會調(diào)用這個表達式來獲取節(jié)點的值，并根據(jù)節(jié)點值的大小來決定它們的順序。

通過 Comparator.comparing() 方法，我們可以將這個 Lambda 表達式作為比較器傳遞給 PriorityQueue 構(gòu)造函數(shù)，以創(chuàng)建一個根據(jù)節(jié)點值排序的優(yōu)先隊列。也就是說，優(yōu)先隊列 q 中的節(jié)點會根據(jù)節(jié)點值的大小進行排序，使得隊列中的節(jié)點始終以升序排列。

通過循環(huán)遍歷 lists 數(shù)組，對每個鏈表進行判斷。如果當前鏈表不為空（即非空鏈表），就將該鏈表的頭節(jié)點（即最小值節(jié)點）加入到優(yōu)先隊列 q 中。

進入循環(huán)，持續(xù)執(zhí)行以下步驟，直到優(yōu)先隊列 q 為空：

• 從優(yōu)先隊列 q 中取出當前最小的節(jié)點，并將其設(shè)為 tail 的下一個節(jié)點。
  將 tail 指向新的節(jié)點。
• 如果 tail.next 不為空，說明當前的已合并鏈表還有剩余節(jié)點。
• 返回新鏈表 dummy 的下一個節(jié)點，即合并后的有序鏈表的頭節(jié)點。