ヒープをわかりやすく解説してみた

基本的なデータ構造であるヒープについて、概要、計算量と実装、そして最もシンプルな応用であるヒープソートを紹介します。MITが講義や資料を公開しているMIT OpenCourseWareのアルゴリズムとデータ構造の講義 が非常にわかりやすかったので、その内容に沿ってまとめました。この記事ではHeaps and Heap Sortの内容を以下の順序で解説します。

1. ヒープの概要
2. ヒープの表現
3. ヒープの構築
4. ヒープの計算量
5. ヒープの実装
6. ヒープソート

1. ヒープの概要

ヒープ (heap) は優先度付きキュー (priority queue) の実装の1つです。優先度付きキューは集合 (set) を扱うデータ型で、集合に含まれる要素が何らかの優先度 (priority) 順に取り出されるという特徴を持っています。学会のポスター発表を回るときや、旅行先での観光地巡りでは、優先度に基づいて要素を取り出すことが重要になります。集合を扱う代表的なデータ型に、スタック (stack) と キュー (queue) がありますが、スタックは末尾 から、キューは先頭から要素が取り出されます。スタックでは要素を追加する毎に要素の優先度が増加し、キューでは減少すると考えると、どちらも優先度付きキューの1種と考えることができます。

2. ヒープの表現

ヒープは木構造の1つで、二分木として表現されます。木構造はポインタや配列を使って実装されます。この記事では下に示すように、配列による実装を用います。配列を用いた実装は空間計算量の観点で、ポインタを用いた実装より優れています。ノードの上の数字が配列のインデックスに対応しています。

上図に示したヒープは最小ヒープ (min heap) と呼ばれ、各ノードがその子ノードより小さいか等しくなっています。

左の図に示したように、最小ヒープにおいて、親ノードとその子ノードに着目したとき、親ノードは必ず最小になります。定義が逆になったものを最大ヒープ (max heap) と呼びます。以下この記事では最小ヒープのことをヒープと呼びます。

配列のインデックスiの親ノードや子ノードへのアクセスは次のように表現できます。

• 根ノード｜i = 1, 配列の先頭の要素
• 親ノード｜parent(i) = i / 2
• 左の子ノード｜left(i) = 2i
• 右の子ノード｜right(i)=2i+1

i = 4のノードに着目すると、親ノードと子ノードは次の図のようになります。

親ノードは、parent(i) = 4 / 2 = 2でインデックス2の要素になります。子ノードは、left(i) = 2 * 2 = 4、right(i) = 2 * 2 + 1 = 5となるので、インデックス8, 9の要素になります。

3. ヒープの構築

任意の配列からヒープを構築するために、2つ操作が必要になります。

1. min_heapify｜あるノードとその配下のノードがヒープの条件を満たすようにする操作
2. build_min_heap｜任意の配列からヒープを作成する操作

各ノードについてmin_heapifyを繰り返し適用することで、ヒープを構築 (build_min_heap) します。

3.1 min_heapify

min_heapifyは、

1. あるノードとその子ノードはヒープの条件を満たさないが、
2. 子ノードとその配下のノードがヒープの条件を満たすとき、

あるノードとその子ノードがヒープの条件を満たすようにノードの交換を行います。1と2を同時に満たす木構造は以下のようになります。

オレンジ色のノードに着目すると、9は2、3の両方より大きいので、ヒープの条件 (子ノードより小さいか等しい) を満たしません。

一方で、青色のノードでは、ヒープの条件を満たしています。

min_heapify(array, index)を木構造を表す配列arrayとインデックスindexを引数にとり、インデックスで指定されたノードとその子ノードがヒープの条件を満たすようにするメソッドと定義します。

上述の木構造をヒープにすることで、min_heapifyの動作を確認します。min_heapify(array, 2)によってインデックス2のノードとインデックス4のノードの配置を交換します。

min_heapify(array, 2)適用後の木構造は以下のようになり、青色のノードに着目するとヒープの条件を満たします。

仮にインデックス5のノードと配置を交換すると、以下のようになりヒープの条件を満たしません。すなわちヒープの条件を満たすためには、着目した3つのノードの内、最小のノードを親ノードとする必要があります。 (これはヒープの条件でもある。)

正しい交換を行った木構造に戻ります。オレンジのノードに着目すると、ヒープの条件を満たしていません。

min_heapify(array, 4)の実行によって、ヒープの条件を満たすようにします。

インデックス4とインデックス8のノードの交換によって、ヒープの条件を満たすようになりました。

以上の操作で条件を満たさない木構造 (配列) をヒープにすることができました。

3.2 build_min_heap

build_min_heapの操作は次のような擬似コードで表されます。

build_min_heap(array)
    for i=n/2 downto 1
        do min_heapify(array, i)

forループで葉ノード以外のノードを根ノードに向かって順に走査し、各ノードに対してmin_heapifyを適用しています。n/2+1以降のノードはすべて葉ノードになるので、min_heapifyを適用する必要がないためです。走査されるノードをオレンジで示すと下図となります。

根ノードに向かってノードを走査するので、min_heapifyを適用できる前提を満たしながら、各ノードがヒープの条件を満たすようにすることができます。例えば、インデックス4, 5にmin_heapifyを適用した後にインデックス2にmin_heapifyが適用されるので、インデックス2の子ノードとその配下のノードがヒープの条件を満たすことになります。

4. ヒープの計算量

ヒープ構築の最悪計算量、すなわちbuild_min_heapの最悪計算量を解説します。まずbuild_min_heapの主な処理であるmin_heapifyの最悪計算量について考えます。

min_heapifyは配列の要素交換 (O(1)) を繰り返す操作のため、繰り返し回数に比例した計算量になります。最悪の繰り返し回数はmin_heapifyを適用した木の高さに一致します。よって根ノードが最終的に最も深い葉ノードを交換される場合に計算回数が多くなります。hを根ノードの高さとするとmin_heapifyの最悪計算量はO(h)となります。

各深さにおけるmin_heapifyの計算量は下図のようになります。各深さにおけるノードの個数も横に示しました。

図からbuild_min_heapの最悪計算量 (すべての内部ノードの計算量の合計) は、

となります。木の高さhを導出できれば良いことがわかります。

各深さにおけるノード数の合計はノードの総数nであるので、

となります。等比数列の和の公式を使ってhは次のようになります。

以上の結果をまとめるとヒープ構築 (build_min_heap) の最悪計算量は、O(n)となります。またmin_heapifyの最悪計算量は、O(log n)となります。

5. ヒープの実装

3で解説したmin_heapifyとbuild_min_heapをPythonで実装します。min_heapifyの実装は以下のようになります。

def min_heapify(array, i):
    left = 2 * i + 1
    right = 2 * i + 2
    length = len(array) - 1
    smallest = i
    if left <= length and array[i] > array[left]:
        smallest = left
    if right <= length and array[smallest] > array[right]:
        smallest = right
    if smallest != i:
        array[i], array[smallest] = array[smallest], array[i]
        min_heapify(array, smallest)

インデックスiのノードと子ノードの中で最小のノードを計算し、最小のノードをインデックスiに配置します。ノードの交換が起こった場合、交換されたノードについてmin_heapifyが適用されます。

Pythonのリスト (配列) のインデックスは0から始まるので、子ノード等のアクセスは次のようになります。

• 根ノード｜i = 0
• 親ノード｜parent(i) = (i-1) / 2
• 左の子ノード｜left(i) = 2i + 1
• 右の子ノード｜right(i)=2i+2

コード中の変数smallestに最小のノードのインデックスが格納されています。smallestがiと一致しない、すなわちヒープの条件を満たさない場合 (if smallest != iがTrue) 、ノードが交換され、smallestのノードに対してmin_heapifyが実行されます。

build_min_heapの実装は疑似コードとほぼ同じで、以下のようになります。

def build_min_heap(array):
    for i in reversed(range(len(array)//2)):
        min_heapify(array, i)

for部分が擬似コードと異なっていますが、インデックスが1から始まるときと同様、葉ノード以外のノードを根ノードに向かって走査しています。

6. ヒープソート

ヒープソートは、ヒープを利用したソートで、min_heapifyとbuild_min_heapによって簡単に実装できます。ソートの流れは次のようになります。なおソート順は昇順です。

1. 任意の配列について、build_min_heapでヒープを作成
2. 配列の先頭と末尾の要素を交換
3. 末尾の要素を配列から削除
4. 先頭の要素 (インデックス0の要素) に対してmin_heapifyを実行
5. 2に戻る

ヒープでは先頭から最小の要素取り出せます。先頭と末尾の要素を入れ替えてから要素を取り出すので、残った配列は先頭の要素に対してmin_heapifyを適用できる条件を満たします。この性質により、「2. 先頭と末尾の入れ替え」、「3. 末尾の要素削除」、「4. 先頭に対するmin_heapifyの適用」を繰り返すことでソートを実現できます。

実装は次のようになります。

def heap_sort(array):
    array = array.copy()
    build_min_heap(array)
    sorted_array = []
    for _ in range(len(array)):
        array[0], array[-1] = array[-1], array[0]
        sorted_array.append(array.pop())
        min_heapify(array, 0)

    return sorted_array

最悪計算量は、min_heapifyを配列の要素数、n回繰り返すことになるのでO(nlogn)となります。

Pythonでは、heapqモジュールにヒープ操作のためのアルゴリズムがすでに実装されています。メソッドは講義に合わせたので、Pythonの実装とは異なっています。詳しいPythonの実装はソースコードをご覧ください。

• heapq.heapify｜build_min_heapに相当
• heapq.heappop | 要素入れ替え、末尾要素の削除、min_heapifyの適用に相当

上記のメソッドを使うと、ヒープソートをドキュメントの実装とは少し異なりますが、以下のように実装できます。

import heapq
def heap_sort(array):
    h = array.copy()
    heapq.heapify(h)
    return [heapq.heappop(h) for _ in range(len(array))]        

まとめは以上になります。