技術提高是一個循序漸進的過程，所以我講的leetcode算法題從最簡單的level開始寫的，然後> 到中級難度，最後到hard難度全部完。目前我選擇C語言，Python和Java作為實現語言，因為這三種語言還是比較典型的。由於篇幅和> 精力有限，其他語言的實現有興趣的朋友請自己嘗試。初級難度說的差不多的時候，我打算再加點其他內容，我可能會從操作系統到協議棧，從分佈式> 聊到大數據框架，從大數據聊到人工智能，... ...。

如果有任何問題可以在文章後評論或者私信給我。

我會持續分享下去，敬請您的關注。

LeetCode 703. 數據流中的第K大元素（Kth Largest Element in a Stream）

問題描述：

設計一個找到數據流中第K大元素的類（class）。注意是排序後的第K大元素，不是第K個不同的元素。你的 KthLargest 類需要一個同時接收整數 k 和整數數組nums 的構造器，它包含數據流中的初始元素。每次調用 KthLargest.add，返回當前數據流中第K大的元素。注:你可以假設 nums 的長度≥ k-1 且k ≥ 1。

示例：

C語言實現：

這是一個簡單的優先隊列問題。所以考慮如何實現優先隊列。

優先隊列實現分為有序實現，和無序實現。

有序實現有普通數組、普通鏈表和普通二叉樹。有序實現包括有序數組，有序鏈表，二叉搜索樹，以及二叉堆。（這裡首先聲明一點，二叉堆並不是真正的有序，或者說不保證任何遍歷是有序的，但是它可以保證最大值或者最小值一點是根節點。）

通常優先隊列的實現也都是用二叉堆，因為二叉堆的綜合性能比較好，即插入，刪除和查找最大值（或最小值）的平均性能比較好。

二叉堆是一種特殊二叉樹，它必須是一個完全二叉樹，這個性質決定 了，二叉堆可以很方便的用數組來實現。而優先隊列要求，最小值（或最大值）位於隊列的頭部（或尾部），方便彈出，而二叉堆的數組存儲形式中，最大值(或最小值)就是數組的第一個元素，可見二叉堆非常適合實現優先隊列。

根據值大小的分佈情況，二叉堆又分為：

• 最小堆：所有節點的值必須小於等於子節點的值, 則最小值在根節點；
• 最大堆：所有節點的值必須大於等於子節點的值, 則最大值在根節點；

如下圖，左邊是最小堆，右邊是最大堆：

如上圖，我們可以將二叉樹從根節點開始從上到小按層從左到右將節點一個個存入數組中，這樣就得到二叉堆數組存儲形式。

觀察後，這樣我們可以得出結論：

1. 如果二叉堆有k個節點，那麼數組的長度也是k.
2. 而對於某個下標為n的節點，它的子節點的下標將會是2n+1和2n+2, 它的父節點下標將是(n-1)/2。

本題是找出第k個最大值，所以適合用最小堆。

我們可以將隊列的容量設置為k，即限制二叉堆所有節點數不超過k個，則第k大的值即整個二叉堆的最小值在根節點。對於第k-1大以後的元素，與本題的解沒有關係，所以忽略。

我們要實現這個過程就需要將元素一個個插入到二叉堆中，這就涉及到二叉堆的堆化。堆化的意義是，當入隊和出隊的時候，可能會使得當前的二叉樹不再是一個二叉堆，堆化就是重新對樹進行調整，讓其再次變成二叉堆。

（下面的描述是針對最小堆，最大堆類似。）

二叉堆的堆化根據方向，分為上浮和下沉兩種情況， 我們針對這道題來說明。

上浮：

當隊列的容量沒有滿的時候，這時候我們插入新元素是直接插入二叉堆的末尾，形成一個新的葉子節點，然後比較父節點和新元素值的大小，如果父節點的值大於新元素，就相互交換，新元素交換後再和新的父節點比較，如此下去。

下沉：

針對本題，當隊列滿的時候，插入一個新元素，且該元素大於二叉堆的根節點時，表示當前的根節點將會變成第k+1個元素，即它不應該再作為二叉堆的根，所以首先，將其出隊，然後用新插入的元素值代替；再拿子節點中值最小的元素和新元素進行比較，如果新元素大，就交換。如此下去。

所以最終可以得出如下的代碼：

注意二叉堆的前中後序遍歷都均無法保證有序性，尤其是是中序遍歷，一定是無序的。但是通常這個並不重要。二叉堆可以保證根節點在整個樹中是最小或最大，這樣就可以了。

Java語言實現：

Java 提供了優先隊列的實現，PriorityQueue，所以我們可以直接使用：代碼如下：

Python語言實現：

雖然 Python 庫中也提供了PriorityQueue，但是不建議用，而是建議用heapq, 理由是：

1. PriorityQueue無法一次完成heapq的heappushpop()的功能，而heappushpop對於這道題來說很方便。
2. 用heapq實現更簡潔。
3. 實際上，PriorityQueue就是對heapq的封裝，在同等條件下，多一層封裝往往意味著多一些消耗。

詳細代碼如下：

謝謝大家一直以來的關注和支持！

我一直在努力的寫好每一篇文章，畫好每一份插圖。但是作為一個996從業人員，時間精力十分有限。所以針對評論部分，以後只回答粉絲的問題和私信。希望僅僅是路過的朋友能夠體諒，希望更多人關注《吾是我師》，謝謝！