leetcode 寻找有序数组的中位数（LeetCode基础算法题第123篇）

技术提高是一个循序渐进的过程，所以我讲的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从业人员，时间精力十分有限。所以针对评论部分，以后只回答粉丝的问题和私信。希望仅仅是路过的朋友能够体谅，希望更多人关注《吾是我师》，谢谢！

,