まるさんかくなブログ

プログラミングを学んでいきたいと思っています。いろいろ試していきたい。ゲームとかもします。

ヒープソート

ヒープソート

久々にソーティングアルゴリズムを勉強していて、なんとなくc言語でコードを書いてみた。

ソースコードはこちらから

ヒープソートの特徴として、
- 木構造
- ヒープが作れなきゃ話にならない
- まあまあ早い(O(nlogn))
といった特徴がある。

ヒープとは

まずそもそもヒープとはなんなのかというと、ある点から見ると二つに別れた木構造となっており、親の点が子の点よりも大きい、または小さい木である（今回は小さい）。
（※メモリ空間のヒープ領域とはまた違うので注意！）

f:id:marusan_tec:20180724152507p:plain

ちなみにヒープの各要素は配列に対応している。
ある点の要素から親と子を探すための計算式は次のようになる。
${ \displaystyle \begin{align} 親 = \frac{i}{2} \end{align} }$ ${ \displaystyle \begin{align} 左の子 = 2 \cdot i \end{align} }$ ${ \displaystyle \begin{align} 右の子 = 2 \cdot i + 1 \end{align} }$

配列の0番目が定義されていないのは、この計算をしたいためで深い意味はない。

ヒープソートのアルゴリズム

ヒープソートの流れを以下に示す。
- 最小値（根）を現在の一番深い右端の葉と交換
- 交換した葉の点は、ヒープから取り除く
- 根から左右の子と比較して大きいならば一番小さい子と交換を繰り返す
- 終わったら最初に戻る
これを繰り返すと配列が大きい順になるはず。

最悪計算時間

ヒープソートの最悪計算時間を知るために、まず木の高さを知る必要がある。
木の高さをh、ソートしたい要素数をnとすると

${ \displaystyle \begin{align} 2^h ≤ n ≤ 2^{h+1} - 1 \end{align} }$

${ \displaystyle \begin{align} h ≤ logn \lt h + 1 \end{align} }$

この関係式が成り立つ。

ここで最悪の場合、最小値と交換した点が木の最大の深さまで交換を行うと考えると、

${ \displaystyle \begin{align} log(n - 1) \end{align} }$

となる（最小値を覗くためn-1）。
これをn個の要素で考えれば、

${ \displaystyle \begin{align} log(n-1) + log(n-2) + \dots+ log2 = log(n-1)! ≤ nlogn \end{align} }$

になるため、全体の最悪計算時間はO(nlogn)となる。

まとめ

今更こんな探せばいくらでも出てくる情報だけれども、まあ備忘録だからいいかな。
思ったよりプログラムを作るのが大変だった。
久々にc言語を触ると色々と忘れてる...