与最大堆和最小堆一样，我想实现中值堆来跟踪给定整数集的中值。 API应具有以下三个功能：
insert(int) // should take O(logN)
int median() // will be the topmost element of the heap. O(1)
int delmedian() // should take O(logN)
我想使用数组 (a) 实现来实现堆，其中数组索引 k 的子项存储在数组索引 2*k 和 2*k + 1 中。为了方便起见，数组从索引 1 开始填充元素。
这是我到目前为止所拥有的：
中位数堆将有两个整数来跟踪到目前为止插入的整数数量，即 > 当前中位数 (gcm) 和
if abs(gcm-lcm) >= 2 and gcm > lcm we need to swap a[1] with one of its children.
The child chosen should be greater than a[1]. If both are greater,
choose the smaller of two.
对于其他情况也是如此。我无法想出如何让元素下沉和游泳的算法。我认为应该考虑数字与中位数的接近程度，例如：
private void swim(int k) {
while (k > 1 && absless(k, k/2)) {
exch(k, k/2);
k = k/2;
}
}
但我无法想出完整的解决方案。
您需要两个堆：一个最小堆和一个最大堆。每个堆包含大约一半的数据。最小堆中的每个元素都大于或等于中位数，最大堆中的每个元素都小于或等于中位数。
当最小堆比最大堆多包含一个元素时，中位数位于最小堆的顶部。当最大堆比最小堆多包含一个元素时，中位数位于最大堆的顶部。
当两个堆包含相同数量的元素时，元素总数为偶数。
在这种情况下，您必须根据中位数的定义进行选择：a）两个中间元素的平均值； b) 两者中较大者； c) 较小的； d) 随机选择两者中的任何一个...
每次插入时，将新元素与堆顶部的元素进行比较，以确定将其插入的位置。如果新元素大于当前中位数，则它将进入最小堆。如果小于当前中位数，则转到最大堆。那么你可能需要重新平衡。如果堆的大小相差多个元素，则从具有更多元素的堆中提取最小/最大，并将其插入到另一个堆中。
为了构建元素列表的中值堆，我们应该首先使用线性时间算法并找到中值。一旦知道了中位数，我们就可以根据中位数简单地将元素添加到最小堆和最大堆中。不需要平衡堆，因为中位数会将输入的元素列表分成相等的两半。
如果提取一个元素，您可能需要通过将一个元素从一个堆移动到另一个堆来补偿大小变化。通过这种方式，您可以确保两个堆始终具有相同的大小或仅相差一个元素。
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
