ソートされたJavaシーケンスを効率的にマージします

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

1. 概要

この短いチュートリアルでは、ヒープを使用して並べ替えられた配列を効率的にマージする方法を説明します。

2. アルゴリズム

問題の説明はヒープを使用して配列をマージすることなので、最小ヒープを使用して問題を解決します。最小ヒープは、各ノードの値がその子ノードの値よりも小さいバイナリツリーに他なりません。

通常、最小ヒープは、ノードの親と子を見つける際に配列が特定のルールを満たす配列を使用して実装されます。

配列A[]およびインデックスiの要素の場合：

A [（i-1）/2]はその親を返します
A [（2 * i）+1]は左の子を返します
A [（2 * i）+2]は正しい子を返します

これが最小ヒープとその配列表現の写真です。

次に、並べ替えられた配列のセットをマージするアルゴリズムを作成しましょう。

すべての入力配列の長さを加算して決定されたサイズで、結果を格納する配列を作成します。
入力配列の数に等しいサイズの2番目の配列を作成し、すべての入力配列の最初の要素をその配列に入力します。
すべてのノードとその子に最小ヒープルールを適用して、以前に作成した配列を最小ヒープに変換します。
結果の配列が完全に入力されるまで、次の手順を繰り返します。
最小ヒープからルート要素を取得し、結果の配列に格納します。
ルート要素を、現在のルートが設定されている配列の次の要素に置き換えます。
min-heap配列にmin-heapルールを再度適用します。

このアルゴリズムには、最小ヒープを作成するための再帰フローがあり、入力配列のすべての要素にアクセスする必要があります。

このアルゴリズムの時間複雑度はO（k log n）、です。ここで、 kはすべての入力配列、およびの要素の総数です。 nは、ソートされた配列の総数です。

問題をよりよく理解できるように、アルゴリズムを実行した後のサンプル入力と期待される結果を見てみましょう。したがって、これらのアレイの場合：

{ { 0, 6 }, { 1, 5, 10, 100 }, { 2, 4, 200, 650 } }

アルゴリズムは結果の配列を返す必要があります。

{ 0, 1, 2, 4, 5, 6, 10, 100, 200, 650 }

3. Javaの実装

最小ヒープとは何か、マージアルゴリズムがどのように機能するかについての基本的な理解ができたので、Javaの実装を見てみましょう。 2つのクラスを使用します。1つはヒープノードを表し、もう1つはマージアルゴリズムを実装します。

3.1. ヒープノード表現

アルゴリズム自体を実装する前に、ヒープノードを表すクラスを作成しましょう。これにより、ノード値と2つのサポートフィールドが保存されます。

public class HeapNode {

    int element;
    int arrayIndex;
    int nextElementIndex = 1;

    public HeapNode(int element, int arrayIndex) {
        this.element = element;
        this.arrayIndex = arrayIndex;
    }
}

ここでは、わかりやすくするために、ゲッターとセッターを意図的に省略していることに注意してください。 arrayIndex プロパティを使用して、現在のヒープノード要素が取得される配列のインデックスを格納します。また、 nextElementIndex プロパティを使用して、ルートノードを結果の配列に移動した後に取得する要素のインデックスを格納します。

最初、nextElementIndexの値は1になります。 min-heapのルートノードを置き換えた後、その値をインクリメントします。

3.2. 最小ヒープマージアルゴリズム

次のクラスは、最小ヒープ自体を表し、マージアルゴリズムを実装することです。

public class MinHeap {

    HeapNode[] heapNodes;

    public MinHeap(HeapNode heapNodes[]) {
        this.heapNodes = heapNodes;
        heapifyFromLastLeafsParent();
    }

    int getParentNodeIndex(int index) {
        return (index - 1) / 2;
    }

    int getLeftNodeIndex(int index) {
        return (2 * index + 1);
    }

    int getRightNodeIndex(int index) {
        return (2 * index + 2);
    }

    HeapNode getRootNode() {
        return heapNodes[0];
    }

    // additional implementation methods
}

min-heapクラスを作成したので、サブツリーのルートノードが配列の指定されたインデックスにあるサブツリーをヒープ化するメソッドを追加しましょう。

void heapify(int index) {
    int leftNodeIndex = getLeftNodeIndex(index);
    int rightNodeIndex = getRightNodeIndex(index);
    int smallestElementIndex = index;
    if (leftNodeIndex < heapNodes.length 
      && heapNodes[leftNodeIndex].element < heapNodes[index].element) {
        smallestElementIndex = leftNodeIndex;
    }
    if (rightNodeIndex < heapNodes.length
      && heapNodes[rightNodeIndex].element < heapNodes[smallestElementIndex].element) {
        smallestElementIndex = rightNodeIndex;
    }
    if (smallestElementIndex != index) {
        swap(index, smallestElementIndex);
        heapify(smallestElementIndex);
    }
}

最小ヒープを表すために配列を使用する場合、最後のリーフノードは常に配列の最後になります。したがって、 heapify（）メソッドを繰り返し呼び出して配列を最小ヒープに変換する場合、最後のリーフの親ノードから反復を開始するだけで済みます。

void heapifyFromLastLeafsParent() {
    int lastLeafsParentIndex = getParentNodeIndex(heapNodes.length);
    while (lastLeafsParentIndex >= 0) {
        heapify(lastLeafsParentIndex);
        lastLeafsParentIndex--;
    }
}

次のメソッドは、アルゴリズムの実際の実装を行います。理解を深めるために、メソッドを2つの部分に分割して、どのように機能するかを見てみましょう。

int[] merge(int[][] array) {
    // transform input arrays
    // run the minheap algorithm
    // return the resulting array
}

最初の部分は、入力配列を、最初の配列のすべての要素を含むヒープノード配列に変換し、結果の配列のサイズを見つけます。

HeapNode[] heapNodes = new HeapNode[array.length];
int resultingArraySize = 0;

for (int i = 0; i < array.length; i++) {
    HeapNode node = new HeapNode(array[i][0], i);
    heapNodes[i] = node;
    resultingArraySize += array[i].length;
}

次の部分では、アルゴリズムのステップ4、5、6、および7を実装して、結果の配列を設定します。

MinHeap minHeap = new MinHeap(heapNodes);
int[] resultingArray = new int[resultingArraySize];

for (int i = 0; i < resultingArraySize; i++) {
    HeapNode root = minHeap.getRootNode();
    resultingArray[i] = root.element;

    if (root.nextElementIndex < array[root.arrayIndex].length) {
        root.element = array[root.arrayIndex][root.nextElementIndex++];
    } else {
        root.element = Integer.MAX_VALUE;
    }
    minHeap.heapify(0);
}

4. アルゴリズムのテスト

ここで、前述したのと同じ入力を使用してアルゴリズムをテストしてみましょう。

int[][] inputArray = { { 0, 6 }, { 1, 5, 10, 100 }, { 2, 4, 200, 650 } };
int[] expectedArray = { 0, 1, 2, 4, 5, 6, 10, 100, 200, 650 };

int[] resultArray = MinHeap.merge(inputArray);

assertThat(resultArray.length, is(equalTo(10)));
assertThat(resultArray, is(equalTo(expectedArray)));

5. 結論

このチュートリアルでは、min-heapを使用してソートされた配列を効率的にマージする方法を学びました。

ここで示した例は、GitHubのにあります。

getdocs

13036