本文主要是介绍76、堆-数据流的中位数，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
思路：
这个问题是动态数据流中位数查找问题。在数据流中，数据是逐个到来的，而我们需要在任何时候快速返回已有数据的中位数。中位数是将数据集分成两个等长的子集，一个包含所有较小的元素而另一个包含所有较大的元素。
为了高效解决这个问题，我们可以使用两个优先队列（堆）：
- 一个最大堆（maxQueue），用来存储当前所有元素中较小的一半，它能够保证在堆顶的是这个子集中最大的元素。
- 一个最小堆（minQueue），用来存储较大的一半，它能够保证在堆顶的是这个子集中最小的元素。
这样设计的原因是：
最大堆和最小堆的堆顶元素可以视为中位数或中位数的候选值，因为这两个元素正好将整个数据集分为两个等长的部分，或者其中一个部分多一个元素（当数据总数是奇数时）。
插入操作（addNum）可以保持两个堆的大小平衡（即数量相等或仅差一个元素），这样可以确保中位数总是处于堆顶，可以在常数时间内被检索到。
当数据总数为偶数时，中位数是两个堆顶元素的平均值；当数据总数为奇数时，中位数是元素多的那个堆的堆顶元素。
在addNum方法中，每次添加一个新元素时，我们首先判断它应该属于哪一个子集：
如果新元素小于等于最大堆的堆顶元素，或者最大堆为空，这意味着这个新元素属于较小的一半，因此应该加入最大堆。
否则，它属于较大的一半，应该加入最小堆。
加入元素后，我们可能需要重新平衡两个堆以确保它们的大小满足要求。如果任一堆的大小超过另一堆的大小超过1，我们将堆顶元素移动到另一堆以恢复平衡。
在findMedian方法中，我们根据两个堆的大小关系来确定中位数：
如果两个堆的大小相等，这意味着元素总数是偶数，我们返回两个堆顶元素的平均值作为中位数。
如果两个堆的大小不等，这意味着元素总数是奇数，我们返回元素较多的那个堆的堆顶元素作为中位数。
整体上，这个设计利用了最大堆和最小堆各自的性质，以及它们在维护中位数方面的互补性，从而提供了一个既高效又简洁的解决方案。
class MedianFinder {// 用于存储较大一半元素的小顶堆。PriorityQueue<Integer> minQueue;// 用于存储较小一半元素的大顶堆。PriorityQueue<Integer> maxQueue;// MedianFinder 类的构造函数。public MedianFinder() {// 初始化 minQueue 为小顶堆。minQueue = new PriorityQueue<>();// 初始化 maxQueue 为大顶堆，使用自定义比较器来逆序元素。maxQueue = new PriorityQueue<>((a, b) -> b - a);}// 将数字添加到数据结构中的方法。public void addNum(int num) {// 如果 maxQueue 是空的，直接将数字添加到 maxQueue。if (maxQueue.isEmpty()) {maxQueue.add(num);} else {// 根据 maxQueue 的顶部元素决定将数字添加到 minQueue 或 maxQueue。if (maxQueue.peek() >= num) {maxQueue.add(num);} else {minQueue.add(num);}}// 如果必要的话，调整堆的大小，确保两个堆的大小差不多于1。if (maxQueue.size() == minQueue.size() + 2) {minQueue.add(maxQueue.poll());}if (minQueue.size() == maxQueue.size() + 2) {maxQueue.add(minQueue.poll());}}// 查找当前添加的数字的中位数的方法。public double findMedian() {// 如果两个堆的大小相同，中位数是它们顶部元素的平均值。if (maxQueue.size() == minQueue.size()) {return (maxQueue.peek() + minQueue.peek()) / 2.0;} else if (maxQueue.size() > minQueue.size()) {// 如果 maxQueue 的元素更多，中位数是 maxQueue 的顶部元素。return maxQueue.peek() * 1.0;} else {// 如果 minQueue 的元素更多，中位数是 minQueue 的顶部元素。return minQueue.peek() * 1.0;}}
}
这篇关于76、堆-数据流的中位数的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
