Javaでのヒープソート
1. 序章
In this tutorial, we’ll see how Heap Sort works, and we’ll implement it in Java.
2. ヒープデータ構造
ヒープは、特殊なツリーベースのデータ構造です。 したがって、ノードで構成されます。 要素をノードに割り当てます。すべてのノードに含まれる要素は1つだけです。
また、ノードは子を持つことができます。 ノードに子がない場合、それをリーフと呼びます。
ヒープが特別にするのは2つのことです。
- すべてのノードの値は、その子に格納されているすべての値以下である必要があります。
- 完全なツリーです。つまり、高さが最小になります。
最初のルールにより、最小要素は常にツリーのルートにあります。
これらのルールをどのように適用するかは、実装によって異なります。
ヒープは、最小（または最大）の要素を抽出する非常に効率的な実装であるため、通常、優先キューを実装するために使用されます。
2.1. ヒープバリアント
ヒープには多くのバリエーションがあり、それらはすべて実装の詳細が異なります。
たとえば、親は常にすべての子よりも小さいため、上記で説明したのは最小ヒープです。 または、Max-Heapを定義することもできます。この場合、親は常に子よりも大きくなります。 したがって、最大の要素はルートノードにあります。
多くのツリー実装から選択できます。 最も簡単なのは二分木です。 バイナリツリーでは、すべてのノードに最大2つの子を含めることができます。これらを左の子および右の子と呼びます。
2番目のルールを適用する最も簡単な方法は、完全な二分木を使用することです。 フルバイナリツリーは、いくつかの簡単なルールに従います。
- ノードに子が1つしかない場合は、それが左の子になります
- 最も深いレベルの右端のノードのみが子を1つだけ持つことができます
- 葉は最も深いレベルにのみ存在することができます
いくつかの例でこれらのルールを見てみましょう：
1 2 3 4 5 6 7 8 9 10
() () () () () () () () () ()
/ \ / \ / \ / \ / \ / / / \
() () () () () () () () () () () () () ()
/ \ / \ / \ / / \
() () () () () () () () ()
/
()木1、2、4、5、7は規則に従います。
ツリー3と6は1番目のルールに違反し、8と9は2番目のルールに違反し、10は3番目のルールに違反します。
このチュートリアルでは、バイナリツリーの実装による最小ヒープに焦点を当てます。
2.2. 要素の挿入
ヒープを不変に保つ方法ですべての操作を実装する必要があります。 このようにして、繰り返し挿入でヒープを構築できるので、単一の挿入操作に焦点を当てます。
次の手順で要素を挿入できます。
- 最も深いレベルで使用可能な右端のスロットである新しいリーフを作成し、そのノードにアイテムを格納します
- 要素が親よりも小さい場合は、それらを交換します
- 要素が親よりも小さくなるか、新しいルートになるまで、手順2に進みます。
ステップ2はヒープルールに違反しないことに注意してください。ノードの値を小さい値に置き換えても、その子よりも小さい値になるためです。
例を見てみましょう！ このヒープに4を挿入します。
2
/ \
/ \
3 6
/ \
5 7最初のステップは、4を格納する新しいリーフを作成することです。
2
/ \
/ \
3 6
/ \ /
5 7 44は親の6よりも小さいので、それらを交換します。
2
/ \
/ \
3 4
/ \ /
5 7 6次に、4が親よりも小さいかどうかを確認します。 親が2なので、やめます。 ヒープはまだ有効であり、番号4を挿入しました。
1を挿入しましょう：
2
/ \
/ \
3 4
/ \ / \
5 7 6 11と4を入れ替える必要があります。
2
/ \
/ \
3 1
/ \ / \
5 7 6 4ここで、1と2を入れ替える必要があります。
1
/ \
/ \
3 2
/ \ / \
5 7 6 41が新しいルートなので、停止します。
3. Javaでのヒープ実装
フルバイナリツリーを使用しているため、配列を使用して実装できます。配列内の要素はツリー内のノードになります。 次のように、すべてのノードに左から右、上から下の配列インデックスを付けます。
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プロパティに違反しません。
要素が葉になるまで、またはすべての子より少なくなるまで、交換を続けます。
このツリーからルートを削除しましょう。
1
/ \
/ \
3 2
/ \ / \
5 7 6 4まず、最後の葉を根に置きます。
4
/ \
/ \
3 2
/ \ /
5 7 6次に、両方の子よりも大きいため、最小の子である2と交換します。
2
/ \
/ \
3 4
/ \ /
5 7 64は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 % o fの要素は葉であり、75% ofの要素は2つの最下層にあります。 したがって、ほとんどの挿入操作は2ステップ以上かかりません。
実際のデータでは、クイックソートは通常、ヒープソートよりもパフォーマンスが高いことに注意してください。 銀の裏打ちは、ヒープソートが常に最悪の場合の O（n log n）時間計算量を持っているということです。
7. 結論
このチュートリアルでは、バイナリヒープとヒープソートの実装を見ました。
時間計算量はO（n log n）ですが、ほとんどの場合、これは実際のデータに最適なアルゴリズムではありません。
いつものように、例はGitHubでから入手できます。
