Javaでヒープを使用する整数ストリームの中央値

投稿日: 2022-10-31 2022-10-31
タグ: Algorithms, Java

1. 概要

このチュートリアルでは、整数のストリームの中央値を計算する方法を学習します。

問題を例で示し、問題を分析し、最後にJavaでいくつかのソリューションを実装します。

2. 問題文

中央値は、順序付けられたデータセットの中央値です。整数のセットの場合、中央値よりも大きい要素と同じ数の要素があります。

順序付けられたセット：

整数の奇数、中央値は中央値です–順序集合 {5、7、10} では、中央値は7です。
偶数の整数の場合、中間要素はありません。中央値は、2つの中間要素の平均として計算されます。順序集合 {5、7、8、10} では、中央値は（7 + 8）/ 2 =7.5[X197Xです。 ]

ここで、有限集合の代わりに、データストリームから整数を読み取っていると仮定しましょう。整数のストリームの中央値をこれまでに読み取られた整数のセットの中央値として定義できます。

問題の説明を形式化しましょう。整数のストリームの入力が与えられた場合、読み取る整数ごとに次の2つのタスクを実行するクラスを設計する必要があります。

整数のセットに整数を追加します
これまでに読み取った整数の中央値を見つけます

例えば：

add 5         // sorted-set = { 5 }, size = 1
get median -> 5

add 7         // sorted-set = { 5, 7 }, size = 2 
get median -> (5 + 7) / 2 = 6

add 10        // sorted-set = { 5, 7, 10 }, size = 3 
get median -> 7

add 8         // sorted-set = { 5, 7, 8, 10 }, size = 4 
get median -> (7 + 8) / 2 = 7.5
..

ストリームは有限ではありませんが、ストリームのすべての要素を一度にメモリに保持できると想定できます。

タスクは、コードで次の操作として表すことができます。

void add(int num);

double getMedian();

3. 素朴なアプローチ

3.1. ソートされたリスト

簡単なアイデアから始めましょう。整数のソートされたlistの中央値は、listの中央の要素または中央の2つの要素にインデックスでアクセスすることで計算できます。 getMedian操作の時間計算量はO（1）です。

新しい整数を追加するときは、 list がソートされたままになるように、list内の正しい位置を決定する必要があります。この操作は、 O（n）時間で実行できます。ここで、nはリストのサイズです。したがって、リストに新しい要素を追加し、新しい中央値を計算するための全体的なコストは、 O（n）です。

3.2. 素朴なアプローチの改善

add 操作は線形時間で実行されますが、これは最適ではありません。このセクションでそれに対処してみましょう。

リストを2つのソートされたリスト– に分割できます。整数の小さい方の半分は降順でソートされ、大きい方の半分は昇順でソートされます。 リストのサイズが最大で1異なるように、適切な半分に新しい整数を追加できます。

if element is smaller than min. element of larger half:
    insert into smaller half at appropriate index
    if smaller half is much bigger than larger half:
        remove max. element of smaller half and insert at the beginning of larger half (rebalance)
else
    insert into larger half at appropriate index:
    if larger half is much bigger than smaller half:
        remove min. element of larger half and insert at the beginning of smaller half (rebalance)

これで、中央値を計算できます。

if lists contain equal number of elements:
    median = (max. element of smaller half + min. element of larger half) / 2
else if smaller half contains more elements:
    median = max. element of smaller half
else if larger half contains more elements:
    median = min. element of larger half

add 操作の時間計算量を一定の要因で改善しただけですが、進歩を遂げました。

2つのソートされたリストでアクセスする要素を分析してみましょう。（ソートされた） add 操作中に要素をシフトするときに、各要素にアクセスする可能性があります。さらに重要なことに、リバランスのための add 操作中、および getMedian 操作中に、大きい方と小さい方の半分の最小値と最大値（極値）にそれぞれアクセスします。

極値がそれぞれのリストの最初の要素であることがわかります。したがって、は、 add 操作の全体的な実行時間を改善するために、ごとにインデックス0の要素にアクセスするように最適化する必要があります。

4. ヒープベースのアプローチ

素朴なアプローチから学んだことを適用して、問題の理解を深めましょう。

O（1）時間でデータセットの最小/最大要素を取得する必要があります
最小/最大要素を効率的に取得できる限り、要素を並べ替えた順序で保持する必要はありません
O（n）時間未満のコストでデータセットに要素を追加するためのアプローチを見つける必要があります

次に、目標を効率的に達成するのに役立つヒープデータ構造を見ていきます。

4.1. ヒープデータ構造

ヒープはデータ構造であり、通常は配列で実装されますが、バイナリツリーと考えることができます。

ヒープは、ヒーププロパティによって制約されます。

4.1.1. Max –ヒーププロパティ

（子）ノードは、その親の値よりも大きい値を持つことはできません。したがって、 max-heap では、ルートノードが常に最大値を持ちます。

4.1.2. Min –ヒーププロパティ

（親）ノードは、その子の値よりも大きい値を持つことはできません。したがって、 min-heap では、ルートノードの値が常に最小になります。

Javaでは、PriorityQueueクラスはヒープを表します。ヒープを使用した最初のソリューションに進みましょう。

4.2. 最初の解決策

単純なアプローチのリストを2つのヒープに置き換えましょう。

要素の大きい方の半分を含み、ルートに最小の要素がある最小ヒープ
要素の小さい方の半分を含み、ルートに最大の要素がある最大ヒープ

これで、最小ヒープのルートと比較することにより、関連する半分に着信整数を追加できます。次に、挿入後、一方のヒープのサイズがもう一方のヒープのサイズと1を超えて異なる場合、ヒープのバランスを取り直して、最大で1のサイズ差を維持できます。

if size(minHeap) > size(maxHeap) + 1:
    remove root element of minHeap, insert into maxHeap
if size(maxHeap) > size(minHeap) + 1:
    remove root element of maxHeap, insert into minHeap

このアプローチでは、2つのヒープのサイズが等しい場合、中央値を両方のヒープのルート要素の平均として計算できます。それ以外の場合、より多くの要素を持つヒープのルート要素は中央値です。

ヒープを表すためにPriorityQueueクラスを使用します。 PriorityQueueのデフォルトのヒーププロパティはmin-heapです。自然な順序の逆を使用するComparator.reverserOrderを使用して、最大ヒープを作成できます。

class MedianOfIntegerStream {

    private Queue<Integer> minHeap, maxHeap;

    MedianOfIntegerStream() {
        minHeap = new PriorityQueue<>();
        maxHeap = new PriorityQueue<>(Comparator.reverseOrder());
    }

    void add(int num) {
        if (!minHeap.isEmpty() && num < minHeap.peek()) {
            maxHeap.offer(num);
            if (maxHeap.size() > minHeap.size() + 1) {
                minHeap.offer(maxHeap.poll());
            }
        } else {
            minHeap.offer(num);
            if (minHeap.size() > maxHeap.size() + 1) {
                maxHeap.offer(minHeap.poll());
            }
        }
    }

    double getMedian() {
        int median;
        if (minHeap.size() < maxHeap.size()) {
            median = maxHeap.peek();
        } else if (minHeap.size() > maxHeap.size()) {
            median = minHeap.peek();
        } else {
            median = (minHeap.peek() + maxHeap.peek()) / 2; 
        }
        return median;
    }
}

コードの実行時間を分析する前に、使用したヒープ操作の時間計算量を見てみましょう。

find-min/find-max        O(1)    

delete-min/delete-max    O(log n)

insert                   O(log n)

したがって、 getMedian 操作は、find-minおよびfind-max関数を必要とするため、 O（1）時間で実行できます。それだけ。 add操作の時間計算量はO（log n） –3つの挿入/削除呼び出しでそれぞれO（ log n）時間。

4.3. ヒープサイズ不変ソリューション

以前のアプローチでは、新しい各要素をヒープのルート要素と比較しました。 heapプロパティを利用して、適切な半分に新しい要素を追加できる、ヒープを使用した別のアプローチを調べてみましょう。

以前のソリューションで行ったように、最小ヒープと最大ヒープの2つのヒープから始めます。次に、条件を導入しましょう。最大ヒープのサイズは常に（n / 2）である必要がありますが、最小ヒープのサイズは（n / 2）または（n / 2）のいずれかです。 + 1、2つのヒープの要素の総数に応じて。つまり、要素の総数が奇数の場合、最小ヒープのみに追加の要素を含めることができます。

ヒープサイズが不変であるため、両方のヒープのサイズが（n / 2）の場合、両方のヒープのルート要素の平均として中央値を計算できます。それ以外の場合、最小ヒープのルート要素は中央値です。

新しい整数を追加する場合、2つのシナリオがあります。

1. Total no. of existing elements is even
   size(min-heap) == size(max-heap) == (n / 2)

2. Total no. of existing elements is odd
   size(max-heap) == (n / 2)
   size(min-heap) == (n / 2) + 1

ヒープの1つに新しい要素を追加し、毎回リバランスすることで、不変条件を維持できます。

リバランスは、最大の要素を最大ヒープから最小ヒープに移動するか、最小の要素を最小ヒープから最大ヒープに移動することによって機能します。このように、ヒープに追加する前に新しい整数を比較していませんが、その後のリバランスにより、小さい方と大きい方の半分の基本的な不変条件を確実に尊重します。

PriorityQueues を使用して、Javaにソリューションを実装しましょう。

class MedianOfIntegerStream {

    private Queue<Integer> minHeap, maxHeap;

    MedianOfIntegerStream() {
        minHeap = new PriorityQueue<>();
        maxHeap = new PriorityQueue<>(Comparator.reverseOrder());
    }

    void add(int num) {
        if (minHeap.size() == maxHeap.size()) {
            maxHeap.offer(num);
            minHeap.offer(maxHeap.poll());
        } else {
            minHeap.offer(num);
            maxHeap.offer(minHeap.poll());
        }
    }

    double getMedian() {
        int median;
        if (minHeap.size() > maxHeap.size()) {
            median = minHeap.peek();
        } else {
            median = (minHeap.peek() + maxHeap.peek()) / 2;
        }
        return median;
    }
}

操作の時間計算量は変わりません： getMedianはO（1）時間かかりますが、addは時間Oで実行されます（log n）まったく同じ操作数。

両方のヒープベースのソリューションは、同様の空間と時間の複雑さを提供します。 2番目のソリューションは賢く、よりクリーンな実装ですが、アプローチは直感的ではありません。一方、最初の解決策は私たちの直感に自然に従うため、add操作の正確さについて推論する方が簡単です。

5. 結論

このチュートリアルでは、整数のストリームの中央値を計算する方法を学びました。いくつかのアプローチを評価し、PriorityQueueを使用してJavaでいくつかの異なるソリューションを実装しました。

いつものように、すべての例のソースコードは、GitHubでから入手できます。

getdocs

13036