Javaで最小-最大ヒープを実装する方法

投稿日: 2022-10-27 2022-10-27
タグ: Data Structures, Java

1. 概要

このチュートリアルでは、Javaに最小-最大ヒープを実装する方法を見ていきます。

2. 最小-最大ヒープ

まず、ヒープの定義と特性を見てみましょう。 min-maxヒープは、最小ヒープと最大ヒープの両方の特性を備えた完全なバイナリツリーです。

上記のように、ツリーの偶数レベルの各ノードはすべての子孫よりも少なく、ツリーの奇数レベルの各ノードはすべての子孫よりも大きく、ルートはレベルにあります。ゼロ。

min-maxヒープ内の各ノードには、通常キーと呼ばれるデータメンバーがあります。 rootはmin-maxヒープ内で最小のkeyを持ち、2番目のレベルの2つのノードの1つは最大のkeyです。最小-最大ヒープ内のXのようなノードごとに：

X が最小（または偶数）レベルの場合、 X.key は、ルートXを持つサブツリー内のすべてのキーの中で最小のキーです。
X が最大（または奇数）レベルの場合、 X.key は、ルートXを持つサブツリー内のすべてのキーの中で最大のキーです。

min-heapまたはmax-heapと同様に、挿入と削除は O（logN）の時間計算量で発生する可能性があります。

3. Javaでの実装

最小-最大ヒープを表す単純なクラスから始めましょう。

public class MinMaxHeap<T extends Comparable<T>> {
    private List<T> array;
    private int capacity;
    private int indicator;
}

上記のように、インジケーターを使用して、配列に追加された最後のアイテムインデックスを把握します。ただし、続行する前に、配列インデックスはゼロから始まることを覚えておく必要がありますが、インデックスはヒープ内の1から始まると想定しています。

次の方法を使用して、左と右の子のインデックスを見つけることができます。

private int getLeftChildIndex(int i) {
   return 2 * i;
}

private int getRightChildIndex(int i) {
    return ((2 * i) + 1);
}

同様に、次のコードによって、配列内のアイテムの親と祖父母のインデックスを見つけることができます。

private int getParentIndex(int i) {
   return i / 2;
}

private int getGrandparentIndex(int i) {
   return i / 4;
}

それでは、単純な最小-最大ヒープクラスの完了を続けましょう。

public class MinMaxHeap<T extends Comparable<T>> {
    private List<T> array;
    private int capacity;
    private int indicator;

    MinMaxHeap(int capacity) {
        array = new ArrayList<>();
        this.capacity = capacity;
        indicator = 1;
    }

    MinMaxHeap(List<T> array) {
        this.array = array;
        this.capacity = array.size();
        this.indicator = array.size() + 1;
    }
}

ここでは、2つの方法で最小-最大ヒープのインスタンスを作成できます。最初に、 ArrayList と特定の容量でアレイを開始し、次に、既存のアレイから最小-最大ヒープを作成します。

それでは、ヒープでの操作について説明しましょう。

3.1. 作成

まず、既存のアレイから最小-最大ヒープを構築する方法を見てみましょう。ここでは、Heapifyアルゴリズムのようないくつかの適応を伴うFloydのアルゴリズムを使用します。

public List<T> create() {
    for (int i = Math.floorDiv(array.size(), 2); i >= 1; i--) {
        pushDown(array, i);
    }
    return array;
}

次のコードのpushDownを見て、上記のコードで正確に何が起こったかを見てみましょう。

private void pushDown(List<T> array, int i) {
    if (isEvenLevel(i)) {
        pushDownMin(array, i);
    } else {
        pushDownMax(array, i);
    }
}

ご覧のとおり、すべての偶数レベルについて、配列アイテムを次のようにチェックします。 pushDownMin。このアルゴリズムは、私たちが使用するヒープダウンのようなものです removeMin と removeMax ：

private void pushDownMin(List<T> h, int i) {
    while (getLeftChildIndex(i) < indicator) {
       int indexOfSmallest = getIndexOfSmallestChildOrGrandChild(h, i);
          //...
          i = indexOfSmallest;
    }
 }

まず、’i’要素の最小の子または孫のインデックスを見つけます。その後、以下の条件で進めます。

最小の子または孫が現在の要素以上である場合、私たちは壊れます。言い換えると、要素の現在の配置はmin-heapのようなものです。

if (h.get(indexOfSmallest - 1).compareTo(h.get(i - 1)) < 0) {
    //...
} else {
    break;
}

最小の子または孫が現在の要素よりも小さい場合、それをその親または祖父母と交換します。

if (getParentIndex(getParentIndex(indexOfSmallest)) == i) {
       if (h.get(indexOfSmallest - 1).compareTo(h.get(i - 1)) < 0) {
          swap(indexOfSmallest - 1, i - 1, h);
          if (h.get(indexOfSmallest - 1)
            .compareTo(h.get(getParentIndex(indexOfSmallest) - 1)) > 0) {
             swap(indexOfSmallest - 1, getParentIndex(indexOfSmallest) - 1, h);
           }
        }
  } else if (h.get(indexOfSmallest - 1).compareTo(h.get(i - 1)) < 0) {
      swap(indexOfSmallest - 1, i - 1, h);
 }

要素「i」の子が見つかるまで、上記の操作を続けます。

それでは、getIndexOfSmallestChildOrGrandChildがどのように機能するかを見てみましょう。とても簡単です！まず、左の子の値が最小であると想定し、それを他の子と比較します。

private int getIndexOfSmallestChildOrGrandChild(List<T> h, int i) {
    int minIndex = getLeftChildIndex(i);
    T minValue = h.get(minIndex - 1);
    // rest of the implementation
}

各ステップで、インデックスがインジケーターよりも大きい場合、最後に見つかった最小値が答えです。

たとえば、min-valueを適切な子と比較してみましょう。

if (getRightChildIndex(i) < indicator) {
    if (h.get(getRightChildIndex(i) - 1).compareTo(minValue) < 0) {
        minValue = h.get(getRightChildIndex(i));
        minIndex = getRightChildIndex(i);
    }
} else {
     return minIndex;
}

次に、順序付けされていない配列から最小-最大ヒープを作成することが正常に機能することを確認するテストを作成しましょう。

@Test
public void givenUnOrderedArray_WhenCreateMinMaxHeap_ThenIsEqualWithMinMaxHeapOrdered() {
    List<Integer> list = Arrays.asList(34, 12, 28, 9, 30, 19, 1, 40);
    MinMaxHeap<Integer> minMaxHeap = new MinMaxHeap<>(list);
    minMaxHeap.create();
    Assert.assertEquals(List.of(1, 40, 34, 9, 30, 19, 28, 12), list);
}

pushDownMax のアルゴリズムは、 pushDownMin のアルゴリズムと同じですが、すべての比較で、演算子が逆になっています。

3.2. 入れる

最小-最大ヒープに要素を追加する方法を見てみましょう。

public void insert(T item) {
    if (isEmpty()) {
        array.add(item);
        indicator++;
    } else if (!isFull()) {
        array.add(item);
        pushUp(array, indicator);
        indicator++;
    } else {
        throw new RuntimeException("invalid operation !!!");
    }
 }

まず、ヒープが空かどうかを確認します。ヒープが空の場合は、新しい要素を追加してインジケーターを増やします。そうしないと、追加された新しい要素によって最小-最大ヒープの順序が変わる可能性があるため、pushUpを使用してヒープを調整する必要があります。

private void pushUp(List<T>h,int i) {
    if (i != 1) {
        if (isEvenLevel(i)) {
            if (h.get(i - 1).compareTo(h.get(getParentIndex(i) - 1)) < 0) {
                pushUpMin(h, i);
            } else {
                swap(i - 1, getParentIndex(i) - 1, h);
                i = getParentIndex(i);
                pushUpMax(h, i);
            }
        } else if (h.get(i - 1).compareTo(h.get(getParentIndex(i) - 1)) > 0) {
            pushUpMax(h, i);
        } else {
            swap(i - 1, getParentIndex(i) - 1, h);
            i = getParentIndex(i);
            pushUpMin(h, i);
        }
    }
}

上記のように、新しい要素はその親を比較し、次のようになります。

親よりも小さい（大きい）ことがわかった場合は、ヒープのルートへのパス上にある最大（最小）レベルの他のすべての要素よりも明らかに小さい（大きい）です。
新しい要素からルートへのパス（最小/最大レベルのみを考慮）は、挿入前と同じように降順（昇順）である必要があります。したがって、このシーケンスに新しい要素をバイナリ挿入する必要があります

それでは、次のようにpushUpMinを見てみましょう。

private void pushUpMin(List<T> h , int i) {
    while(hasGrandparent(i) && h.get(i - 1)
      .compareTo(h.get(getGrandparentIndex(i) - 1)) < 0) {
        swap(i - 1, getGrandparentIndex(i) - 1, h);
        i = getGrandparentIndex(i);
    }
}

技術的には、親が大きいうちに新しい要素をその親と交換する方が簡単です。また、 pushUpMaxはpushUpMinと同じですが、すべての比較で、演算子が逆になっています。

次に、min-maxヒープへの新しい要素の挿入が正常に機能することを確認するためのテストを作成しましょう。

@Test
public void givenNewElement_WhenInserted_ThenIsEqualWithMinMaxHeapOrdered() {
    MinMaxHeap<Integer> minMaxHeap = new MinMaxHeap(8);
    minMaxHeap.insert(34);
    minMaxHeap.insert(12);
    minMaxHeap.insert(28);
    minMaxHeap.insert(9);
    minMaxHeap.insert(30);
    minMaxHeap.insert(19);
    minMaxHeap.insert(1);
    minMaxHeap.insert(40);
    Assert.assertEquals(List.of(1, 40, 28, 12, 30, 19, 9, 34),
      minMaxHeap.getMinMaxHeap());
}

3.3. 最小を見つける

min-maxヒープのメイン要素は常にルートにあるため、時間計算量O（1）で見つけることができます。

public T min() {
    if (!isEmpty()) {
        return array.get(0);
    }
    return null;
}

3.4. マックスを探す

min-maxヒープのmax要素は常に最初の奇数レベルにあるため、簡単な比較で時間計算量O（1）で見つけることができます。

public T max() {
    if (!isEmpty()) {
        if (indicator == 2) {
            return array.get(0);
        }
        if (indicator == 3) {
            return array.get(1);
        }
        return array.get(1).compareTo(array.get(2)) < 0 ? array.get(2) : array.get(1);
    }
    return null;
}

3.5. 最小値を削除

この場合、min要素を見つけて、それを配列の最後の要素に置き換えます。

public T removeMin() {
    T min = min();
    if (min != null) {
       if (indicator == 2) {
         array.remove(indicator--);
         return min;
       }
       array.set(0, array.get(--indicator - 1));
       array.remove(indicator - 1);
       pushDown(array, 1);
    }
    return min;
}

3.6. マックスを削除

max要素の削除は、remove minの削除と同じですが、max要素のインデックスを見つけて、pushDownを呼び出すだけの変更があります。

public T removeMax() {
    T max = max();
    if (max != null) {
        int maxIndex;
        if (indicator == 2) {
            maxIndex = 0;
            array.remove(--indicator - 1);
            return max;
        } else if (indicator == 3) {
            maxIndex = 1;
            array.remove(--indicator - 1);
            return max;
        } else {
            maxIndex = array.get(1).compareTo(array.get(2)) < 0 ? 2 : 1;
        }
        array.set(maxIndex, array.get(--indicator - 1));
        array.remove(indicator - 1);
        pushDown(array, maxIndex + 1);
    }
    return max;
}

4. 結論

このチュートリアルでは、Javaにmin-maxヒープを実装し、最も一般的な操作のいくつかを調べました。

最初に、最も一般的な機能のいくつかを含め、最小-最大ヒープが正確に何であるかを学びました。次に、min-maxヒープの実装でアイテムを作成、挿入、find-min、find-max、remove-min、およびremove-maxする方法を確認しました。

いつものように、この記事で使用されているすべての例は、GitHubでから入手できます。

getdocs

13036