42

Max-heap と Min-heap のように、Median-heap を実装して、特定の整数セットの中央値を追跡したいと考えています。API には、次の 3 つの機能が必要です。

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 から要素の入力を開始します。これは次のとおりです。私がこれまでに持っているもの: 中央ヒープには、これまでに挿入された整数の数を追跡するための 2 つの整数があり、現在の中央値 (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;
    }
}

しかし、私は完全な解決策を思いつくことはできません。

4

6 に答える 6

175

最小ヒープと最大ヒープの 2 つのヒープが必要です。各ヒープには、データの約半分が含まれます。最小ヒープ内のすべての要素は中央値以上であり、最大ヒープ内のすべての要素は中央値以下です。

最小ヒープに最大ヒープよりも 1 つ多くの要素が含まれている場合、中央値は最小ヒープの一番上にあります。また、最大ヒープに最小ヒープよりも 1 つ多くの要素が含まれている場合、中央値は最大ヒープの一番上にあります。

両方のヒープに同じ数の要素が含まれている場合、要素の総数は偶数です。この場合、中央値の定義に従って選択する必要があります。a) 中央の 2 つの要素の平均。b) 2 つのうち大きい方。c) 少ない方; d) 2 つのいずれかをランダムに選択します...

挿入するたびに、新しい要素をヒープの一番上にある要素と比較して、挿入する場所を決定します。新しい要素が現在の中央値より大きい場合、最小ヒープに移動します。現在の中央値よりも小さい場合は、最大ヒープに移動します。その後、リバランスが必要になる場合があります。ヒープのサイズが複数の要素で異なる場合は、より多くの要素を含むヒープから最小/最大を抽出し、それを他のヒープに挿入します。

要素のリストの中央ヒープを構築するには、まず線形時間アルゴリズムを使用して中央値を見つける必要があります。中央値が分かれば、中央値に基づいて最小ヒープと最大ヒープに要素を追加するだけです。中央値は要素の入力リストを均等に半分に分割するため、ヒープのバランスを取る必要はありません。

要素を抽出する場合、1 つの要素をあるヒープから別のヒープに移動して、サイズの変化を補正する必要がある場合があります。このようにして、常に両方のヒープのサイズが同じか、1 つの要素だけが異なるようにします。

于 2013-03-10T06:30:05.290 に答える
3

comocomocomocomo から提供された回答に基づく私のコードは次のとおりです。

import java.util.PriorityQueue;

public class Median {
private  PriorityQueue<Integer> minHeap = 
    new PriorityQueue<Integer>();
private  PriorityQueue<Integer> maxHeap = 
    new PriorityQueue<Integer>((o1,o2)-> o2-o1);

public float median() {
    int minSize = minHeap.size();
    int maxSize = maxHeap.size();
    if (minSize == 0 && maxSize == 0) {
        return 0;
    }
    if (minSize > maxSize) {
        return minHeap.peek();
    }if (minSize < maxSize) {
        return maxHeap.peek();
    }
    return (minHeap.peek()+maxHeap.peek())/2F;
}

public void insert(int element) {
    float median = median();
    if (element > median) {
        minHeap.offer(element);
    } else {
        maxHeap.offer(element);
    }
    balanceHeap();
}

private void balanceHeap() {
    int minSize = minHeap.size();
    int maxSize = maxHeap.size();
    int tmp = 0;
    if (minSize > maxSize + 1) {
        tmp = minHeap.poll();
        maxHeap.offer(tmp);
    }
    if (maxSize > minSize + 1) {
        tmp = maxHeap.poll();
        minHeap.offer(tmp);
    }
  }
}
于 2017-03-04T04:36:50.697 に答える
2

上記の comomocomomocomo のアイデアに従って、Scala の実装を次に示します。

class MedianHeap(val capacity:Int) {
    private val minHeap = new PriorityQueue[Int](capacity / 2)
    private val maxHeap = new PriorityQueue[Int](capacity / 2, new Comparator[Int] {
      override def compare(o1: Int, o2: Int): Int = Integer.compare(o2, o1)
    })

    def add(x: Int): Unit = {
      if (x > median) {
        minHeap.add(x)
      } else {
        maxHeap.add(x)
      }

      // Re-balance the heaps.
      if (minHeap.size - maxHeap.size > 1) {
        maxHeap.add(minHeap.poll())
      }
      if (maxHeap.size - minHeap.size > 1) {
        minHeap.add(maxHeap.poll)
      }
    }

    def median: Double = {
      if (minHeap.isEmpty && maxHeap.isEmpty)
        return Int.MinValue
      if (minHeap.size == maxHeap.size) {
        return (minHeap.peek+ maxHeap.peek) / 2.0
      }
      if (minHeap.size > maxHeap.size) {
        return minHeap.peek()
      }
      maxHeap.peek
    }
  }
于 2016-10-31T08:27:07.977 に答える
2

完全にバランスの取れた二分探索木 (BST) はメジアン ヒープではありませんか? 赤黒の BST でさえ、常に完全にバランスが取れているわけではありませんが、目的には十分近いかもしれません。そして、log(n) のパフォーマンスが保証されています!

AVL ツリーは、赤黒の BST よりも厳密にバランスが取れているため、真の中央ヒープにさらに近づきます。

于 2013-03-10T09:47:26.887 に答える