アルゴリズムのモヤモヤをPythonで解消(6): ヒープソート

##### [前回] [アルゴリズムのモヤモヤをPythonで解消(5): マージソート](https://qiita.com/mingchun_zhao/items/29850c6fa514a2840e1f)

## はじめに

`Pythonでアルゴリズムを楽しむ`、第6弾です。

## 今回のアルゴリズム: ヒープソート

### 問題

以下8つの数字を昇順で整列せよ。
`8	4	3	7	6	5	2	1`

### 解決案

ヒープソートを使用し、解決します。
その前に、理論知識のおさらいから。

#### データ構造: 木構造(きこうぞう、tree structure)

- 一つの要素(ノード)が複数の子要素を持ち、
    - 一つの子要素が複数の孫要素を持ち、
        - という形で階層が深くなるほど枝分かれしていく構造

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2523098/b27a5428-7d64-2005-b7c4-85d67568895f.png)

- 節(ノード)
    - 各要素(データ)
        - 根でも葉でもないノードは節点
- 根(ルート)
    - 最上位のノード
    - 木構造に一つだけ存在
- 葉(リーフ)
    - 最下位のノード
- 枝(ブランチ)
    - 各ノードを関係づける線

#### データ構造: 2分木

- 子ノードの数を2個以下に限定した木構造
    - 全2分木
        - 子ノードの数が必ず2個
        ![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2523098/85d57496-4e48-311d-e615-f5ca06b91e7c.png)

    - 完全2分木
        - 根から葉までの全ての深さが同じか1つしか違わない

#### データ構造: ヒープ(heap)

- 下記制約を持つ木構造
    - 子要素は親要素より常に大きいか等しい(または常に小さいか等しい)

#### データ構造: 二分ヒープ木

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2523098/b23897cd-12b3-72cb-e3b1-aadd850ff3a7.png)

- 二分木を使って作られる、ヒープ構造の単純な種類のひとつ
- 二分木に、以下の2つの制約を追加したもの
    - 要素間の順序関係に従った比較によって、各ノードはそのノードの子よりも小さいか等しくなるように配置される(heap property)
    - 木は完全にバランスの取れた二分木(すべての葉は同じ深さにある)になるか、木のもっとも高い方がすべて埋まっていないならば、ノードは左から右へ順に埋まっていく(shape property)

#### ヒープソートとは

- Wikipediaから[ヒープソート(heap sort)](https://ja.wikipedia.org/wiki/%E3%83%92%E3%83%BC%E3%83%97%E3%82%BD%E3%83%BC%E3%83%88)
    - リストの並べ替えを二分ヒープ木を用いて行うソートのアルゴリズム
        - ※ メモリ空間のヒープ領域とは無関係
    - 計算量は、O($n\ log\ {n}$)
    - 安定ソートではない
    - データの出現順序による計算量の変化が小さい（クイックソートでは最悪の場合O($n^{2}$)となってしまう
        - ただし、平均的にはクイックソートより遅い
    - ソート対象のデータ自体以外に、必要作業領域の大きさは固定で、データ量に依存しない
        - ただし、並列化できない
    - ヒープ構造はメモリへのアクセスが連続しておらず、ランダムアクセスとなり、空間的局所性が低い
        - 空間的局所性とは
            - プロセッサがあるメモリー領域のコードを要求したとき、
            - プロセッサが次に要求するのは、
            - その次のメモリー領域や付近のメモリー領域である可能性が高いという性質

- ヒープソートの計算量
    - 最悪計算時間: O($n\ log\ {n}$)
    - 最良計算時間: $\Omega(n)$
        - 関数の下界を表すためのオーダー記号$\Omega$(オメガ)
    - 平均計算時間: O($n\ log\ {n}$)

### コード

Pythonの[heapqモジュール](https://docs.python.org/3.6/library/heapq.html)を使用します。

```heap_sort.py
from heapq import heappush
from heapq import heappop
import math
from io import StringIO

PRINT_WIDTH = 50

def print_heap(heap):
    str_buf = StringIO()
    last_level = -1
    for idx, val in enumerate(heap):
        if idx:
            level = int(math.floor(math.log(idx + 1, 2)))
        else:
            level = 0
        if level != last_level:
            str_buf.write('\n')
        col_num = 2 ** level
        col_width = int(math.floor((PRINT_WIDTH * 1.0) / col_num))
        str_buf.write(str(val).center(col_width, ' '))
        last_level = level
    print ('-------------------------  二分ヒープ木  -------------------------')
    print (str_buf.getvalue())
    print ('------------------------------------------------------------')
    return

def heap_sort(arr):
    heap = []
    print('======================  ヒープソート開始  ======================')
    print('初期値: ', end='')
    print(arr)
    for idx in range(len(arr)):
        print('=> %dを配列から取り出し、ヒープに入れる' % arr[idx])
        heappush(heap, arr[idx])
        print_heap(heap)
        print('配列: ', end='')
        print(arr[idx + 1:])
    new_arr = []
    for idx in range(len(heap)):
        popped = heappop(heap)
        print('=> %dをヒープから取り出し、配列に入れる' % popped)
        print_heap(heap)
        new_arr.append(popped)
        print('配列: ', end='')
        print(new_arr)
    print('======================  ヒープソート終了  ======================')

if __name__ == '__main__':
    arr = [8, 4, 3, 7, 6, 5, 2, 1]
    heap_sort(arr)
```

- 実行
```
$ python heap_sort.py
```
- 結果
    - 配列の値を、二分ヒープ木に以下規則で配置してから、再度取り出すと、結果ソートされる
        - `各ノードはその子ノードより小さい`
```
======================  ヒープソート開始  ======================
初期値: [8, 4, 3, 7, 6, 5, 2, 1]
=> 8を配列から取り出し、ヒープに入れる
-------------------------  二分ヒープ木  -------------------------

                        8
------------------------------------------------------------
配列: [4, 3, 7, 6, 5, 2, 1]
=> 4を配列から取り出し、ヒープに入れる  <- 4が8よりちいさいためルートとなる
-------------------------  二分ヒープ木  -------------------------

                        4
            8
------------------------------------------------------------
配列: [3, 7, 6, 5, 2, 1]
=> 3を配列から取り出し、ヒープに入れる   <- 3が4,8よりちいさいためルートとなる
-------------------------  二分ヒープ木  -------------------------

                        3
            8                        4
------------------------------------------------------------
配列: [7, 6, 5, 2, 1]
=> 7を配列から取り出し、ヒープに入れる  <- 7が、8の親ノード、3の子ノードとなる
-------------------------  二分ヒープ木  -------------------------

                        3
            7                        4
     8
------------------------------------------------------------
配列: [6, 5, 2, 1]
=> 6を配列から取り出し、ヒープに入れる  <- 6が、7の親ノート、3の子ノードとなる
-------------------------  二分ヒープ木  -------------------------

                        3
            6                        4
     8           7
------------------------------------------------------------
配列: [5, 2, 1]
=> 5を配列から取り出し、ヒープに入れる  <- 5が、4の子ノードとなる
(※ 二分ヒープ木のため深さのバランスを取りながら左から右へ埋めていく)
-------------------------  二分ヒープ木  -------------------------

                        3
            6                        4
     8           7           5
------------------------------------------------------------
配列: [2, 1]
=> 2を配列から取り出し、ヒープに入れる
-------------------------  二分ヒープ木  -------------------------

                        2
            6                        3
     8           7           5           4
------------------------------------------------------------
配列: [1]
=> 1を配列から取り出し、ヒープに入れる
-------------------------  二分ヒープ木  -------------------------

                        1
            2                        3
     6           7           5           4
  8
------------------------------------------------------------
配列: []    <- 配列が空になったので
=> 1をヒープから取り出し、配列に入れる  <- 一番小さいルートを取り出す、1の子ノードがルートに
(※ 取り出すときも、二分ヒープ木の深さのバランスを取りながら位置調整する)
-------------------------  二分ヒープ木  -------------------------

                        2
            6                        3
     8           7           5           4
------------------------------------------------------------
配列: [1]
=> 2をヒープから取り出し、配列に入れる
-------------------------  二分ヒープ木  -------------------------

                        3
            6                        4
     8           7           5
------------------------------------------------------------
配列: [1, 2]
=> 3をヒープから取り出し、配列に入れる
-------------------------  二分ヒープ木  -------------------------

                        4
            6                        5
     8           7
------------------------------------------------------------
配列: [1, 2, 3]
=> 4をヒープから取り出し、配列に入れる
-------------------------  二分ヒープ木  -------------------------

                        5
            6                        7
     8
------------------------------------------------------------
配列: [1, 2, 3, 4]
=> 5をヒープから取り出し、配列に入れる
-------------------------  二分ヒープ木  -------------------------

                        6
            8                        7
------------------------------------------------------------
配列: [1, 2, 3, 4, 5]
=> 6をヒープから取り出し、配列に入れる
-------------------------  二分ヒープ木  -------------------------

                        7
            8
------------------------------------------------------------
配列: [1, 2, 3, 4, 5, 6]
=> 7をヒープから取り出し、配列に入れる
-------------------------  二分ヒープ木  -------------------------

                        8
------------------------------------------------------------
配列: [1, 2, 3, 4, 5, 6, 7]
=> 8をヒープから取り出し、配列に入れる
-------------------------  二分ヒープ木  -------------------------

------------------------------------------------------------
配列: [1, 2, 3, 4, 5, 6, 7, 8]
======================  ヒープソート終了  ======================
```

## おわりに

Pythonで`ヒープソート`アルゴリズムを解いてみました。
次回も続きます。お楽しみに。