毎月アルゴリズム – 第5回 –

はじめに

こんにちは。よっしーです。
毎月アルゴリズムを考えていくブログの第 5 回目です。
前回はシェルソート、マージソート、クイックソートのアルゴリズムを見ていきました。
今回ヒープソートを紹介して、ソートに関するアルゴリズムは終了としようと思います。

データ構造

第 3 回までで、線形のデータ構造を説明しました。
今回はグラフデータ構造と言われる、ヒープと二分探索木に関して解説していきたいと思います。

ヒープ

ヒープは優先度付きキューの実装の一つです。
優先度付きキューは集合 (set) を扱うデータ型で、集合に含まれる要素が何らかの優先度 (priority) 順に取り出されるという特徴を持っています。
キューとスタックに関しては、以前の記事で説明しました。
キューとスタックも優先度付きキューの 1 種と考えることができます。
(FIFO と LIFO がそれに当たります)

データ構造の特徴は以下です

  1. 分岐点の頂点を「ノード」と呼ぶ
  2. ノードは子ノードを 2 つまで持てる
  3. 頂点のノードの値は子のノードよりも小さい値をとる
  4. ノードは上詰め、同じ段では左詰めになる

構造上、一番頂点のノードは常に最小の値となります。

探索

ヒープ構造では子要素間の大小関係に制約が無いため、目的とする要素が見つかるまで全要素を順に調べる必要がある。
したがって、任意のデータを探索する必要がある場合にヒープ構造を使うことは勧められない。

追加

  1. 末尾(ツリーで見ると一番右下)にノードを追加
  2. 親ノードと比較し、親ノード以上の数値ならそのまま
  3. 親ノードの方が大きければ親子を入れ替え、2 を繰り返す

取り出し

  1. 頂点のノードを取り出す(最小値)
  2. 末尾(ツリーで見ると一番右下)のノードを頂点に持っていく
  3. そのノードと子ノードと比較する。子ノードが存在しないかすべての子ノードの比較結果が比較している数字以上なら終了
  4. 小さい方の子ノードと元のノードを入れ替えて、更に子ノードと比較をする(3 を繰り返す)

再構築にかかる時間

追加したり取り出したりする場合、ノードの順番を入れ替える作業をヒープの再構築と呼びます。
(ツリーを再構築しているように見えますよね)
データ数が n とすると、ツリーの高さは高々 logn となります。

上図より、
2^0 + 2^1 + 2^2 + \cdots + 2^{k-1} = n
\frac{2^k - 1}{2 - 1} = n
2^k = n + 1
k = log(n + 1)
となり、ツリーにフルでノードが詰まっていた場合でも高さは log(n+1) なので、高さは高々 logn としても大丈夫です。
高さが logn になるので、追加、取り出しを行ったときの交換は logn 回起こるので、再構築にかかる時間は O(logn) となります。

まとめ

  1. ヒープは優先度付きキューの一種
  2. 常に先頭ノードに最小値が格納されているため、最小値の取得は O(1)
  3. 追加、取出後の再構築にかかる時間は O(logn)
  4. ヒープはデータの探索には向かない構造である

二分探索木

二分探索木はグラフの木構造を利用しています。
以下 2 つの特徴を持ちます。

  1. すべてのノードはそのノードの左部分木に含まれるどの数字よりも大きくなる
  2. すべてのノードはその右部分木よりも小さくなる

意味不明だと思いますので、例によって図を使って説明します。
二分探索木において、どのノードも必ず左の子ノード < 親のノード < 右の子ノードの関係になっています。
不等号には等号をどちらか片方につけても問題はありません。(今回の記事ではわかりやすさのため省略しています)

更に、ノードだけではなく、そのノードにある配下も全て親ノードより大きい、または小さいという性質があります。
左部分木 < 親のノード < 右部分木

その性質により、最小値は一番左にあるノード、最大値は一番右にあるノードということが決定します。

追加

  1. 最上部のノードと比較して小さければ左の子ノードに進む、大きければ右の子ノードに進む
  2. ノードが存在していれば、そのノードと比較して小さければ左の子ノードに進む、大きければ右の子ノードに進む
  3. 2 でノードが存在しないところまで到達すれば、新しいノードとしてその要素を加える

削除

子ノードが無いノードを削除した場合

  1. ノードを削除

子ノードを持つノードを削除した場合

  1. ノードを削除
  2. 削除したノードの左部分木の最大値を持ってきて移動させる
  3. 2 で左部分木に値がなくなるまで繰り返す

探索

  1. 最上部のノードと比較して小さければ左の子ノードに進む、大きければ右の子ノードに進む。一致していれば終了
  2. 子ノードと比較して小さければ左の子ノードに進む、大きければ右の子ノードに進む
  3. 2 を一致するノードが見つかるまで行なう

計算量

追加、探索において、計算量は高さ分回数を比較することがおわかりいただけると思います。
ヒープのときに見たようにバランス良く木が構成されている場合、 O(logn) で計算可能となりますが、左右のどちらかに偏ってしまう場合、1 直線に並ぶことになり、 O(n) のコストがかかってしまいます。

まとめ

  1. 二分探索木は木構造をとっている
  2. 必ず 左の子ノード < 親のノード < 右の子ノードの関係になっている
  3. 必ず 左部分木 < 親のノード < 右部分木の関係になっている
  4. 追加、探索の最良計算量は O(logn), 最悪計算量は O(n)

アルゴリズムを考えてみる

本日は以下のソートに関してアルゴリズムを考えていきます。

  • ヒープソート

ヒープソート

概要

ヒープソートはデータ構造のヒープを利用してソートを行う方法です。
ヒープの項でほぼ説明は完了しているのですが、ヒープの構造では常に頂点のノードが最小値となるように構築しているので、それを取得し続けることでソートを完了します。

オーダー

ヒープソートははじめにヒープを構成する必要があり、ヒープを構築するのに O(logn) という話をしました。
n 個の要素を繰り返し構築するので、 O(nlogn) となります。
その後、各ラウンドで最大の数を取り出して、再構築する手順を挟むので、ソートにかかる時間は O(nlogn) です。
それらを総合することで、ヒープソートの計算時間は全体で O(nlogn) です。

処理

処理はヒープソートの構築に記載したとおりです。
そのため本項は省略します。

コード

いつもどおりヒープソートのコードを C#で書きました。
Program.cs

HeapSort.cs

おわりに

今回でソートに関するアルゴリズムは終了です。
次回からは探索系のアルゴリズムを考えていく予定です。
よろしければまたご覧になってください。

第0回 (初歩的な数学のアルゴリズムを考えてみよう)
第1回
第2回
第3回
第4回

最近の記事

  • 関連記事
  • おすすめ記事
  • 特集記事

アーカイブ

カテゴリー

PAGE TOP