您需要两个堆：一个最小堆和一个最大堆。每个堆包含大约一半的数据。最小堆中的每个元素均大于或等于中位数，最大堆中的每个元素均小于或等于中位数。
当最小堆比最大堆多包含一个元素时，中位数位于最小堆的顶部。并且当最大堆比最小堆多包含一个元素时，中值位于最大堆的顶部。
当两个堆包含相同数量的元素时，元素总数为偶数。在这种情况下，您必须根据中位数的定义进行选择：a）两个中间元素的平均值；b）两者中较大者；c）较小者；d）随机选择两个…
每次插入时，将新元素与堆顶部的元素进行比较，以决定将其插入的位置。如果新元素大于当前中位数，则转到最小堆。如果小于当前中位数，则转到最大堆。然后，您可能需要重新平衡。如果堆的大小相差一个以上元素，请从具有更多元素的堆中提取最小值/最大值，然后将其插入另一堆。
为了构造元素列表的中值堆，我们应该首先使用线性时间算法并找到中值。一旦知道中位数，我们就可以根据中位数简单地将元素添加到最小堆和最大堆中。不需要平衡堆，因为中位数会将元素的输入列表分成相等的两半。
如果提取元素，则可能需要通过将一个元素从一个堆移动到另一个堆来补偿大小变化。这样，您可以始终确保两个堆的大小相同或仅相差一个元素。
