[Python] 2分ヒープ (1)

2分ヒープ

2分ヒープを理解して、Pythonで実装します。

まず、heap とは、「積み重なった山のようなもの」です。a heap of stones と言えば、石が山のように積み重なっているものです。

ヒープソートは、この山のように積み重なったものの一番上のところから、一つずつものを取っていくイメージです。

二分ヒープ(にぶんヒープ,バイナリヒープ,Binary heap)とは、二分木を使って作られるヒープ(データ構造)の特に単純な種類のひとつである。それは、二分木に、以下の2つの制約を追加したものとみなせる。

出典: フリー百科事典『ウィキペディア(Wikipedia)』

以下の動画を参照します。

2.6.3 Heap – Heap Sort – Heapify – Priority Queues

木構造と配列

まずは、配列を以下のルールに従い木構造で表現することを考えます。

インデックス i のノードがあるとして、

  • そのノードの左側の子のインデックスは 2 * i
  • そのノードの右側の子のインデックスは 2 * i + 1
  • そのノードの親のインデックスは i / 2 (切り下げる)

例えば、以下のような配列を考えます。

index1234567
ABCDEFG

この配列は、以下の木構造で表現されます。

ノードBを例にすると、左の子Dのインデックスは 2*2=4、右の子Eのインデックスは2*2+1=5、親のAのインデックスは 2/2=1 と上のルールを満たします。

以下のような配列を考えます。

index12345
ABCDE

この配列は、以下の木構造で表現されます。

この木構造も、ちゃんと上のルールを満たしています。

以下のような配列を考えます。

index1234567
ABCFG

この配列は、以下の木構造で表現されます。

ノードCを例にすると、左の子Fのインデックスは 3*2=6、右の子Gのインデックスは3*2+1=7、親のAのインデックスは 3/2=1(切り下げ) と上のルールを満たします。

完全2分木

動画の説明と異なりますが、完全2分木 ‘complete binary tree’ とは、一番下のレベル以外は、ノードが全て埋まっており、また一番下のレベルのノードがある場合は、可能な限り左側に寄っている2分木です。

In a complete binary tree every level, except possibly the last, is completely filled, and all nodes in the last level are as far left as possible. It can have between 1 and 2h nodes at the last level h.[18]

complete binary tree

以下は、完全2分木です。

完全2分木

以下も、完全2分木です。

完全2分木

以下は、左側が空いてしまっており、完全2分木ではありません。

また、全てのノードが埋まっている場合、高さは log n で表すことができます。

ヒープ

ヒープとは、完全2分木であり、 それぞれのノードがそのノードの子よりも大きい(または小さい)という順序関係を満たすようになっているものです。

それぞれのノードがそのノードの子よりも大きい場合は max heap 、小さい場合は min heap と呼びます。

max heap

max heap の例です。

max heap は、それぞれのノードがそのノードの子よりも大きくなります。

また、ルートが一番大きくなります。

index1234567
5030201510816

min heap

min heap の例です。

min heap は、それぞれのノードがそのノードの子よりも小さくなります。

また、ルートが一番小さくなります。

index1234567
10302035403225

以下では、max heap を考えます。

ノードの挿入

挿入は、まず完全2分木のルールを守るようにノードの挿入場所を確保し、それから順序関係を満たすようにノードの入れ替えを行うという順番で行われます。

以下の木に max heap の条件を満たすように、60を挿入することを考えます。

index12345678
5030201510816

この場合、まずは、配列の一番右側 index 8 に60を挿入します。

index12345678
503020151081660

その後、下の方から親と値を比較して、親の方が小さい場合は、入れ替えを行います。

入れ替えが終わると、以下のようになります。

index12345678
605020301081615

この入れ替えは、「木の高さ」だけ行われます。木の高さは log n なので O (log n) で挿入を行うことができます。

また、挿入は、「下から上」という方向で行われます。

ノードの削除

heap からは、ルートだけが削除できます。

heap つまり、山のような積み重なったもの から、一番上のものを取り除くイメージです。

ルートを削除してから、まずは、完全2分木のルールを守るように、一番最後のノードをルートに持ってきて、それから順序関係を満たすようにノードの入れ替えを行うという順番で行われます。

以下から50を削除します。

index1234567
5030201510816

50の場所が空きます。

index1234567
30201510816

50の場所に、一番最後の16を持ってきます。

index1234567
16302015108

順序関係を満たすように、ノードの入れ替えを行います。

まず子の比較を行います。

30と20では、30の方が大きいので、入れ替えが必要な場合は30を親と入れ替えます。

次に、親と子を比較します。

30と16では、30のほうが大きいので、入れ替えを行います。

この比較・入れ替えを、上から下にどんどんと進めるイメージです。

続いて、子供の15と10を比較すると15の方が大きいです。

15と16を比較すると、16の方が大きいので、入れ替えの必要はありません。

今回の場合は、一度入れ替えるだけで順序関係が満たされました。

index1234567
30162015108

今回も、入れ替えは、最悪「木の高さ」だけ行われます。木の高さは log n なので、O (log n) で削除を行うことができます。

ここで、削除した値を、空いた場所に入れると考えます。

例えば、今回の場合は、最初に60が削除され以下のようになります。

index1234567
3016201510860

次は30が削除され以下のようになります。

index1234567
2016815103060

次は20が削除され以下のようになります。

index1234567
1615810203060

この調子で全て削除していくと、最終的には、以下のようなソートされた配列を得ることができます。

これがヒープソートと呼ばれるソート方法です。

index1234567
8101516203060

ヒープソート

ヒープソートは以下の順番で行われます。

  1. ヒープを作る。
  2. ヒープから全ての値を削除する。

下の配列を使ってヒープソートを行ってみます。

index12345
1020153040

まずは10を挿入します。

index12345
10

次に20を挿入します。

index12345
1020

順序関係が保たれるように、10と20を交換します。

この流れで、値を挿入していくと、最終的に以下のようになります。

index12345
4030151020

ここまでで、n 個のノードを挿入するのに、それぞれのノードで log n 回の操作が必要になり、ヒープの作成で n * log n の時間がかかります。

ここから、ノードの削除を行います。

まずは40を削除し、20をルートに持ってきて、さらに順序関係を満たすように入れ替えを行います。

削除した40は配列の空いたスペースに持ってきます。

index12345
3020151040

続いて30を削除し、10をルートに持ってきて、順序関係を満たすように入れ替えを行います。

index12345
2010153040

この流れで削除していくと、最終的に以下のような、ソートされた配列を得ることができます。

index12345
1015203040

削除についても挿入と同じく、n 個のノードを削除するのに、それぞれのノードで log n 回の操作が必要になり、ヒープの作成で n * log n の時間がかかります。

つまり、ヒープソートは O (n log n) になります。

heapify

heapify は、配列からのヒープの生成を部分木ことに見て行う方法です。

index1234567
10201512402518

一番最後のノードから、そのノードをルートと考えて、ヒープ構造を満たしているかを確認していきます。

最初は18で、これは単独のノードなので、ヒープ構造を満たしています。

25、40、12も、18と同じく、単独のノードで、ヒープ構造を満たしています。

次に15に進みます。

15はヒープ構造を満たないので、15と25の入れ替えが発生します。

index1234567
10202512401518

20に進みます。

これもヒープ構造を満たさず、20と40の入れ替えが発生します。

下のようになります。

index1234567
10402512201518

10に進みます。

これもヒープ構造を満たさず、10と40の入れ替えを行います。

index1234567
40102512201518

続いて、10と20の入れ替えを行います。

以下のように、ヒープを満たす構造が完成します。

index1234567
40202512101518

以前の方法では、ノードの挿入を行うたびに木の調整を行いましたが、この方法では、木を生成してから、部分木ごとにヒープ構造が守られているかの確認・調整を行います。

優先度付きキュー

また、ヒープを使うことで、優先度付きキューを作ることができます。

優先度付きキュー(ゆうせんどつき -、: priority queue)は、以下の4つの操作をサポートする抽象データ型である。
キューに対して要素を優先度付きで追加する。
– 最も高い優先度を持つ要素をキューから取り除き、それを返す。
– (オプション) 最も高い優先度を持つ要素を取り除くことなく参照する。
– (オプション) 指定した要素を取り除くことなく優先度を変更する

出典: フリー百科事典『ウィキペディア(Wikipedia)』

通常のキューは、FIFOで処理されますが、優先度付きキューは、優先度の高いものから順に処理をしていくキューです。

「最も高い優先度を持つ要素をキューから取り除き、それを返す」という処理は、ヒープの削除操作そのものです。

2分ヒープを使うことで、要素の挿入・削除をO(log n)、先頭の参照や取得はO(1)で行うことができる優先度付きキューになります。

以下に続きます。

前回からの続きです。 Python では、heapq によりheapがモジュールとして提供されているので、普段はこちらを使います。 heapq--- ヒープキューアルゴリズム ここでは、学習のため、前回の内容に沿って、Python で heap を...