1.はじめに

このチュートリアルでは、Heap Sortのしくみを説明し、それをJavaで実装します。

  • ヒープソートはヒープデータ構造に基づいています** ヒープソートを正しく理解するために、最初にヒープとそれらがどのように実装されているかを掘り下げます。

2.ヒープデータ構造

ヒープは

特殊なツリーベースのデータ構造

です。したがって、それはノードで構成されています。要素をノードに割り当てます。各ノードに含まれる要素は1つだけです。

また、ノードは子を持つことができます。ノードに子がない場合は、リーフと呼びます。

ヒープが特別にしているのは2つのことです。

  1. すべてのノードの値は、そのノードに格納されているすべての値以下にする必要があります

子供

。それは

完全な木** です。つまり、可能な限り低い高さです

1番目の規則のため、

最小要素は常にツリーのルートになります

。

これらの規則をどのように適用するかは実装に依存します。

ヒープは、最小（または最大）の要素を抽出する非常に効率的な実装であるため、通常、優先度キューを実装するために使用されます。

2.1. ヒープバリアント

ヒープには多くのバリエーションがありますが、それらはすべて実装の細部が異なります。

たとえば、上で説明したのは

Min-Heapです。親は常にそのすべての子

よりも小さいからです。別の方法として、Max-Heapを定義することもできます。この場合、親は常に子よりも大きくなります。したがって、最大の要素はルートノードになります。

私たちは多くの木の実装から選ぶことができます。最も簡単なのは二分木です。 ** 二分木では、すべてのノードは最大で2つの子を持つことができます。

2番目のルールを強制する最も簡単な方法は、Full Binary Treeを使うことです。フルバイナリツリーはいくつかの簡単な規則に従います。

  1. ノードに子が1つしかない場合は、それが左の子になる

  2. 最も深いレベルの一番右のノードだけが1つだけ持つことができます

子
。葉は最も深いレベルにしかあり得ない

いくつかの例を挙げてこれらの規則を見てみましょう。 

  1        2      3        4        5        6         7         8        9       10
 ()       ()     ()       ()       ()       ()        ()        ()       ()       ()
        /        \    / \    / \    / \     / \     /      /      / \
        ()         ()   ()  ()   ()  ()   ()  ()    ()  ()    ()       ()       ()  ()
                               /         \      / \     / \    /      / \
                               ()          ()     ()  ()    ()  ()   ()       ()  ()
                                                                            /                                                                            ()

木1、2、4、5、7は規則に従います。

ツリー3と6は1番目のルールに違反し、8と9は2番目のルールに違反し、10は3番目のルールに違反します。

このチュートリアルでは、バイナリツリーを使用したMin-Heap実装に焦点を当てます。

2.2. 要素を挿入する

ヒープの不変式を維持する方法で、すべての操作を実装する必要があります。こうすることで、** 繰り返し挿入してヒープを構築することができるので、単一の挿入操作に焦点を当てます。

次の手順で要素を挿入できます。

  1. 最も深いスロットの一番右にある新しいリーフを作成します

そのノードのアイテムを平準化して格納する
。要素が親の要素より小さい場合は、それらを交換します。

  1. 要素がその親または要素より小さくなるまで、手順2に進みます

新しいルートになる

ノードの値を小さい値に置き換えても、それは子の値より小さくなるので、ステップ2はヒープルールに違反しません。

例を見てみましょう。このヒープに4を挿入します。 

        2
      /\
     /  \
     3     6
   /\
   5   7

最初のステップは、4を格納する新しいリーフを作成することです。 

        2
      /\
     /  \
     3     6
   /\  /   5   7 4

4は親の6より小さいので、6を入れ替えます。 

        2
      /\
     /  \
     3     4
   /\  /   5   7 6

それでは、4が親よりも小さいかどうかを調べます。その親は2なので、やめます。ヒープはまだ有効です、そして我々は4番を挿入しました。

1を挿入しましょう: 

        2
      /\
     /  \
     3     4
   /\  /\
   5   7 6   1

1と4を交換する必要があります。 

        2
      /\
     /  \
     3     1
   /\  /\
   5   7 6   4

それでは、1と2を入れ替えましょう。 

        1
      /\
     /  \
     3     2
   /\  /\
   5   7 6   4

1が新しいルートなので、やめます。

3. Javaでのヒープ実装

Full Binary Treeを使用しているので、それを配列** で実装することができます。配列内の要素はツリー内のノードになります。次のように、左から右、上から下の配列インデックスですべてのノードをマークします。 

        0
      /\
     /  \
     1     2
   /\  /   3   4 5

必要なのは、ツリーに格納されている要素の数を追跡することだけです。これにより、挿入したい次の要素のインデックスが配列のサイズになります。

このインデックスを使用して、親ノードと子ノードのインデックスを計算できます。

  • 親:

    （インデックス – 1）/2

  • 左の子:

    2 ** インデックス1

  • 右の子:

    2 ** インデックス+ 2

配列の再割り当てを気にしたくないので、実装をさらに単純化し、

ArrayList

を使用します。

基本的なバイナリツリーの実装は次のようになります。 

class BinaryTree<E> {

    List<E> elements = new ArrayList<>();

    void add(E e) {
        elements.add(e);
    }

    boolean isEmpty() {
        return elements.isEmpty();
    }

    E elementAt(int index) {
        return elements.get(index);
    }

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

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

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

}

上記のコードは新しい要素をツリーの最後に追加するだけです。

したがって、必要に応じて新しい要素を上に移動する必要があります。次のコードでそれを行うことができます。 

class Heap<E extends Comparable<E>> {

   //...

    void add(E e) {
        elements.add(e);
        int elementIndex = elements.size() - 1;
        while (!isRoot(elementIndex) && !isCorrectChild(elementIndex)) {
            int parentIndex = parentIndex(elementIndex);
            swap(elementIndex, parentIndex);
            elementIndex = parentIndex;
        }
    }

    boolean isRoot(int index) {
        return index == 0;
    }

    boolean isCorrectChild(int index) {
        return isCorrect(parentIndex(index), index);
    }

    boolean isCorrect(int parentIndex, int childIndex) {
        if (!isValidIndex(parentIndex) || !isValidIndex(childIndex)) {
            return true;
        }

        return elementAt(parentIndex).compareTo(elementAt(childIndex)) < 0;
    }

    boolean isValidIndex(int index) {
        return index < elements.size();
    }

    void swap(int index1, int index2) {
        E element1 = elementAt(index1);
        E element2 = elementAt(index2);
        elements.set(index1, element2);
        elements.set(index2, element1);
    }

   //...

}

要素を比較する必要があるので、

java.util.Comparable

を実装する必要があります。

4.ヒープソート

ヒープのルートは常に最小の要素を含んでいるので、

Heap Sortの背後にある考え方は非常に単純です。ヒープが空になるまでルートノードを削除します

必要なのは削除操作だけです。これは、ヒープを一貫した状態に保ちます。バイナリツリーやヒーププロパティの構造に違反しないようにする必要があります。

  • 構造を維持するために、右端の葉以外の要素を削除することはできません。そのため、ルートノードから要素を削除し、右端の葉をルートノードに格納することをお勧めします。

しかし、この操作は最も確実にHeapプロパティに違反します。そのため、** 新しいルートがその子ノードのいずれよりも大きい場合は、最小の子ノードと交換します。最小の子ノードは他のすべての子ノードよりも小さいため、Heapプロパティに違反しません。

要素が葉になるまで、または要素のすべての子より少なくなるまでスワップし続けます。

このツリーからルートを削除しましょう。 

        1
      /\
     /  \
     3     2
   /\  /\
   5   7 6   4

まず、最後の葉を根に置きます。 

        4
      /\
     /  \
     3     2
   /\  /   5   7 6

それから、それはその子の両方よりも大きいので、我々はそれをその最小の子と交換します。それは2です: 

        2
      /\
     /  \
     3     4
   /\  /   5   7 6

4は6未満なので、停止します。

5. Javaでのヒープソートの実装

これで、ルートを削除（ポップ）することができます 

class Heap<E extends Comparable<E>> {

   //...

    E pop() {
        if (isEmpty()) {
            throw new IllegalStateException("You cannot pop from an empty heap");
        }

        E result = elementAt(0);

        int lasElementIndex = elements.size() - 1;
        swap(0, lasElementIndex);
        elements.remove(lasElementIndex);

        int elementIndex = 0;
        while (!isLeaf(elementIndex) && !isCorrectParent(elementIndex)) {
            int smallerChildIndex = smallerChildIndex(elementIndex);
            swap(elementIndex, smallerChildIndex);
            elementIndex = smallerChildIndex;
        }

        return result;
    }

    boolean isLeaf(int index) {
        return !isValidIndex(leftChildIndex(index));
    }

    boolean isCorrectParent(int index) {
        return isCorrect(index, leftChildIndex(index)) && isCorrect(index, rightChildIndex(index));
    }

    int smallerChildIndex(int index) {
        int leftChildIndex = leftChildIndex(index);
        int rightChildIndex = rightChildIndex(index);

        if (!isValidIndex(rightChildIndex)) {
            return leftChildIndex;
        }

        if (elementAt(leftChildIndex).compareTo(elementAt(rightChildIndex)) < 0) {
            return leftChildIndex;
        }

        return rightChildIndex;
    }

   //...

}

前に述べたように、ソートは単にヒープを作成し、繰り返しルートを削除することです。 

class Heap<E extends Comparable<E>> {

   //...

    static <E extends Comparable<E>> List<E> sort(Iterable<E> elements) {
        Heap<E> heap = of(elements);

        List<E> result = new ArrayList<>();

        while (!heap.isEmpty()) {
            result.add(heap.pop());
        }

        return result;
    }

    static <E extends Comparable<E>> Heap<E> of(Iterable<E> elements) {
        Heap<E> result = new Heap<>();
        for (E element : elements) {
            result.add(element);
        }
        return result;
    }

   //...

}

次のテストでうまくいっていることを確認できます。 

@Test
void givenNotEmptyIterable__whenSortCalled__thenItShouldReturnElementsInSortedList() {
   //given
    List<Integer> elements = Arrays.asList(3, 5, 1, 4, 2);

   //when
    List<Integer> sortedElements = Heap.sort(elements);

   //then
    assertThat(sortedElements).isEqualTo(Arrays.asList(1, 2, 3, 4, 5));
}

  • その場でソートする実装を提供することができます。つまり、要素を取得したのと同じ配列で結果を提供します。

さらに、この方法では、中間のメモリ割り当ては不要です。

しかしながら、その実装は理解するのが少し難しいでしょう。

6.時間の複雑さ

ヒープソートは

2つの重要なステップ

、

要素の挿入

とルートノードの削除** で構成されています。両方のステップとも、複雑さが

O（log n）

です。

  • 両方のステップをn回繰り返すので、全体のソートの複雑さは

    O（n log n）

    です。

配列の再割り当てのコストについては触れていませんが、これは

O（n）

なので、全体の複雑さには影響しません。また、前述したように、インプレースソートを実装することも可能です。つまり、配列の再割り当ては不要です。

また、言及する価値があるのは、要素の50％が葉で、要素の75％が2つの最下位レベルにあるということです。したがって、ほとんどの挿入操作では、2つ以上の手順を踏む必要はありません。

  • 実際のデータでは、Quicksortは通常Heap Sortよりもパフォーマンスが優れています。銀の内張りは、ヒープソートは常に最悪の場合

    O（n log n）

    時間の複雑さを持つということです。

7.まとめ

このチュートリアルでは、Binary HeapとHeap Sortの実装を見ました。

  • 時間の複雑さは

    O（n log n）

    ですが、ほとんどの場合、これは現実のデータに対する最良のアルゴリズムではありません。**

いつものように、例はhttps://github.com/eugenp/tutorials/tree/master/algorithms-sorting[GitHubについて]で利用可能です。