パスワードを忘れた? アカウント作成
16351819 journal
日記

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 は、子ノード(右)を表す。

ヒープデータ構造の特徴としてはこのぐらいか。

問題は、テキトーな配列を与えられたとして、このデータ構造をどうやって作るかということになる。

この議論は賞味期限が切れたので、アーカイブ化されています。 新たにコメントを付けることはできません。
typodupeerror

Stableって古いって意味だっけ? -- Debian初級

読み込み中...