数据流中的中位数（priority_queue）1

数据流中的中位数是一个常见的算法问题，主要目标是设计一个数据结构，它能有效地处理不断到来的新数据，并随时返回当前数据流的中位数。在这个问题中，我们使用了两个优先级队列（priority_queue）来实现这个功能。优先级队列是一种特殊的容器，可以保证插入和删除元素的时间复杂度为O(log n)，并且总是能保持队列中的元素满足特定的排序规则。 在C++中，`priority_queue`通常基于堆实现，这里我们用到了两个堆，一个大根堆（left），一个小根堆（right）。大根堆存储较小的数，而小根堆存储较大的数。这种设计使得大根堆的堆顶元素是所有元素中的最小值，小根堆的堆顶元素是所有元素中的最大值。 具体实现上，`MedianFinder`类有以下几个关键部分： 1. 初始化构造函数：`MedianFinder()`，在这里我们可以不进行任何操作，因为两个优先级队列在初始状态下都是空的。 2. `addNum(int num)`方法：这个方法用于接收新的数据并将其添加到合适的堆中。我们检查新数据`num`与大根堆的堆顶元素`left.top()`的关系。如果`num`小于或等于堆顶元素，我们将其添加到大根堆；否则，我们将其添加到小根堆。然后，为了保持左右两堆的平衡，我们需要检查它们的大小。如果左堆比右堆大一个以上，我们将左堆的堆顶元素移动到右堆；反之，如果右堆比左堆大一个以上，我们将右堆的堆顶元素移动到左堆。这样可以确保在任何时候，较大的堆都包含较小堆的元素个数加一，从而确保中位数的正确性。 3. `findMedian()`方法：此方法返回当前数据流的中位数。我们检查左右堆的总元素个数是否为奇数。如果是奇数，中位数就是较大堆的堆顶元素；如果是偶数，中位数是两个堆顶元素的平均值。注意，由于C++的浮点数除法可能会导致精度问题，所以在计算平均值时，我们将两个堆顶元素相加后再除以2.0，以确保结果是一个浮点数。 这个解决方案在处理大规模数据流时具有较高的效率，因为它仅在添加新数据时进行有限的调整，并且这些调整的时间复杂度较低。此外，由于我们使用了优先级队列，查找中位数的时间复杂度也为O(1)。 在给定的示例中，我们看到如何使用这个`MedianFinder`类。例如，在第一个示例中，我们创建了一个`MedianFinder`对象，然后依次添加了数字1、2和3。每次添加数字后，我们调用`findMedian`方法获取中位数。初始时，由于没有数据，中位数无法确定。添加1后，中位数是1；添加2后，中位数是1.5（(1+2)/2）；最后添加3后，中位数变成了2。第二个示例展示了类似的过程，但数据流的中位数在添加3后变为2.5，因为现在有两个元素（2和3），它们的平均值是2.5。 通过这个方法，我们可以有效地处理动态的数据流，并实时计算其中的中位数，这对于实时数据分析和统计应用非常有用。