ヒープソート

ヒープ構造とは、簡単に言うと、2分木の各節点にデータを保持し、親のデータが2つの子のデータよりも小さくなるように作られたデータ構造です。すべてのデータの中で、木の根のデータがもっとも小さいことが保障されますから、最小値データを取り出すことや、データの追加が最悪でも log(N) 時間で行えるという、優れた特徴があります。 ヒープソートの基本的な考え方は、与えられたデータを順にヒープ構造に追加して行き、すべてのデータを追加し終わったら根から取り出すと言うものです。 ヒープ構造は、もっとも小さいデータが常に根にあることが特徴です。したがって、すべてのデータをヒープに追加してから、根から順に取り出せば、小さい順にデータを取り出すことが可能です。ただし、データの追加や取り出しのときは、ヒープ構造が壊れないように注意しなければなりません。 ヒープにデータを追加するときは、まず木構造の最後に追加します

[Ehren]

あとでErlangで実装する