一、題目介紹
今天要練習的是LeetCode 215：Kth Largest Element in an Array

題目給定一個整數陣列nums和一個整數k，要求找出陣列中第k大的元素

例如：
nums = [3,2,1,5,6,4]
k = 2

將數字由大到小排列：[6,5,4,3,2,1]
第 2 大的元素就是：5
因此答案為：5

二、解題想法：Heap
這題可以使用Heap（堆積）解決
Heap是一種特殊的樹狀資料結構，可以快速取得目前的最大值或最小值。
這次我們使用的是：Min Heap（最小堆）

雖然題目要求的是「第 k 大」，但使用Min Heap反而非常方便
我們只需要讓Heap裡面最多維持k個元素

例如：
nums = [3,2,1,5,6,4]
k = 2

依序加入數字：3
Heap：[3]
加入 2：[2,3]
加入 1：[1,3,2]
因為現在有超過k = 2個元素，所以移除最小值：[2,3]
接著加入 5：[2,3,5]
超過兩個，再移除最小值：[3,5]
繼續加入 6：[3,5,6]
移除最小值：[5,6]
最後加入 4：[4,5,6]
再移除最小值：[5,6]
最後 Heap 最小的元素就是：5
也就是第2大的元素

三、為什麼使用Min Heap？
這題最容易讓人疑惑的地方就是：「我要找第k大，為什麼不用Max Heap？」

其實Max Heap當然也可以做，但如果使用Min Heap，我們可以把Heap控制在只有k個元素
例如找：第3大
我們就只保留目前遇到的最大的3個數字
而這3個數字中最小的那個，就是第3大

例如：[10, 8, 7]
其中：
10 → 第 1 大
8 → 第 2 大
7 → 第 3 大
Min Heap的最小值就是：7

因此維持大小為k的Min Heap，最後Heap頂端就是第k大元素

四、Java實作

五、Python實作

六、時間與空間複雜度
假設陣列有n個元素

時間複雜度
每個元素最多進入Heap一次，每次Heap操作需要O(log k)
因此總時間複雜度為O(n log k)

空間複雜度
Heap最多只保存k個元素：O(k)
所以不需要建立一個和整個陣列一樣大的額外資料結構

七、Java與Python比較

八、實作結果
Leetcode測試結果：Accepted

九、今日學習心得
今天第一次使用Heap來解決問題，和前幾天的Backtracking有很不一樣的感覺。之前的題目比較著重於「如何探索所有可能性」，而這次則是利用資料結構來快速維持我們需要的資訊。

一開始看到「第 k 大」時，我想到的方法可能會是先把陣列排序，再找到對應的位置。不過學習Heap之後，可以發現其實不一定要把所有數字完整排序。

這題使用Min Heap，並且讓Heap的大小最多維持k個元素。當新的數字加入後，如果超過k個，就把最小的數字移除。經過整個陣列後，留下來的就是最大的k個元素，而其中最小的那一個就是第k大。

這讓我了解到，選擇適合的資料結構可以讓演算法更加有效率。Java的PriorityQueue和Python的heapq雖然操作方式不同，但都可以很方便地實作Min Heap。

今天也開始理解Heap不只是「排序工具」，而是一種可以快速取得最小值或最大值的資料結構。之後遇到Top K、優先順序或需要持續維持最大／最小元素的問題時，就可以想到Heap。