如何实现中位数堆

  • Z时代
  • 2024-01-10
  • 分类：问答

像最大堆和最小堆一样，我想实现中位数堆来跟踪给定整数集的中位数。该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）和<当前中位数（lcm）。

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）随机选择两个…

每次插入时，将新元素与堆顶部的元素进行比较，以决定将其插入的位置。如果新元素大于当前中位数，则转到最小堆。如果小于当前中位数，则转到最大堆。然后，您可能需要重新平衡。如果堆的大小相差一个以上元素，请从具有更多元素的堆中提取最小值/最大值，然后将其插入另一堆。

为了构造元素列表的中值堆，我们应该首先使用线性时间算法并找到中值。一旦知道中位数，我们就可以根据中位数简单地将元素添加到最小堆和最大堆中。不需要平衡堆，因为中位数会将元素的输入列表分成相等的两半。

如果提取元素，则可能需要通过将一个元素从一个堆移动到另一个堆来补偿大小变化。这样，您可以始终确保两个堆的大小相同或仅相差一个元素。

以上是 如何实现中位数堆 的全部内容， 来源链接： utcz.com/qa/410443.html

回到顶部