如何实现平均堆 [英] How to implement a Median-heap

问题描述

就像一个最大堆和民堆，我想实现一个平均堆跟踪给定整数的位数。该API应具有以下三个功能：

Like a Max-heap and Min-heap, I want to implement a Median-heap to keep track of the median of a given set of integers. The API should have the following three functions:

insert(int)  // should take O(logN)
int median() // will be the topmost element of the heap. O(1)
int delmedian() // should take O(logN)

我想用一个数组（一）实施2 * k和2 * K + 1，为方便起见，该阵列开始从指数1填充的元素来实现，其中数组索引k的孩子都存储在数组索引堆。 这是我到目前为止有： 的平均堆将有两个整数跟踪到目前为止是插入整数数目的>电流中位数（GCM）和＆lt;目前的中位数（LCM）。

I want to use an array (a) implementation to implement the heap where the children of array index k are stored in array indices 2*k and 2*k + 1. For convenience, the array starts populating elements from index 1. This is what I have so far: The Median-heap will have two integers to keep track of number of integers inserted so far that are > current median (gcm) and < current median (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.

类似地，对于其它情况。我不能拿出一个算法如何下沉和游泳的元素。我认为应该考虑如何关闭数量的中位数，所以是这样的：

Similarly for the other case. I can't come up with an algorithm for how to sink and swim elements. I think it should take into consideration how close the number is to the median, so something like:

private void swim(int k) {
    while (k > 1 && absless(k, k/2)) {   
        exch(k, k/2);
        k = k/2;
    }
}

我不能拿出完整的解决方案，但。

I can't come up with the entire solution though.

推荐答案

您需要两个堆：1分钟堆，一个最大堆。每堆包含约一半的数据。在最小堆的每个元素是大于或等于中值，而在最大堆的每个元素是小于或等于的中位数。

You need two heaps: one min-heap and one max-heap. Each heap contains about one half of the data. Every element in the min-heap is greater or equal to the median, and every element in the max-heap is less or equal to the median.

在最小堆包含一个比最大堆更多元，中位数是最小堆的顶部。而当最大堆包含一个比最小堆更元件，中值是在最大堆的顶部。

When the min-heap contains one more element than the max-heap, the median is in the top of the min-heap. And when the max-heap contains one more element than the min-heap, the median is in the top of the max-heap.

当两个堆包含元素的数相同，元件的总数是偶数。 在这种情况下，你必须根据你的中位数的定义选择：1）中间的两个元素的平均值; b）该两者的更大; C）较小的; d）在随机选择任意两个...

When both heaps contain the same number of elements, the total number of elements is even. In this case you have to choose according your definition of median: a) the mean of the two middle elements; b) the greater of the two; c) the lesser; d) choose at random any of the two...

您插入每一次，以确定在哪里插入它比那些在堆顶部的新元素。如果新的元素是大于当前位数，这是不言而喻的最小堆。如果它小于当前正中，它进入最大堆。这时，你可能需要重新平衡。如果堆的大小相差超过一种元素，从具有多个元件堆提取最小值/最大值，并将其插入其他堆

Every time you insert, compare the new element with those at the top of the heaps in order to decide where to insert it. If the new element is greater than the current median, it goes to the min-heap. If it is less than the current median, it goes to the max heap. Then you might need to rebalance. If the sizes of the heaps differ by more than one element, extract the min/max from the heap with more elements and insert it into the other heap.

为了构建位数堆元素列表，首先要使用线性时间算法，找到中值。一旦中位数是已知的，我们可以简单的添加元素的基础上的中值的最小堆和最大堆。平衡堆不需要因为位数将元件的输入列表分成相等的两半。

In order to construct the median heap for a list of elements, we should first use a linear time algorithm and find the median. Once the median is known, we can simply add elements to the Min-heap and Max-heap based on the median value. Balancing the heaps isn't required because the median will split the input list of elements into equal halves.

如果您提取元素，你可能需要通过将一个元素从一个堆到另一种，以弥补尺寸变化。这样可以确保在任何时候，无论堆的大小相同或相差只有一个元素。

If you extract an element you might need to compensate the size change by moving one element from one heap to another. This way you ensure that, at all times, both heaps have the same size or differ by just one element.

这篇关于如何实现平均堆的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！