yuuka_maniaの日記: ヒープ(順序木)さらに、ヒープソート
日記 by
yuuka_mania
アニメーションがあった。作りたいけど、かなり大変そうだ。
https://www.cs.usfca.edu/~galles/JavascriptVisual/Heap.html
参考資料
https://medium.com/@yasufumy/data-structure-heap-ecfd0989e5be
ヒープソートを語る前に、ヒープデータ構造についての知識がないといけない。
ヒープは、二分木の順序木で、親ノードが、子ノードより小さいという特徴を持つ。(もちろん大きくてもいいが、小さいを前提とする)
要は、一定の決まりで、整理、構築された木ということ。これは、直感的にわかりやすい。親ノードが小さいので、 root ノードは、一番小さい値となっている。
ビジュアルの表現としては、木でも、実際は、一定の順序の配列としてデータを保持して、プログラムを書くこともできる。 index 0 は、root ノードで、
index 1, 2 は、上から二段目のノードといった具合に。
二分木なので、最上段を root として(つまり、最小値)、最下段のノード数(保持可能数)は、全体の半分を占める。
ノード数 / 2 は、最下段から一段上の右端のノードを指す配列の index になる。
(自分ノードの index - 1) / 2 は、親ノードを表す
自分ノードの index * 2 + 1 は、子ノード(左)を表す。(もちろん、子がいる状態であれば)
自分ノードの index * 2 + 2 は、子ノード(右)を表す。
ヒープデータ構造の特徴としてはこのぐらいか。
問題は、テキトーな配列を与えられたとして、このデータ構造をどうやって作るかということになる。
ヒープ(順序木) More ログイン