パソコン素人です。
データ構造素人です。
基本情報技術者試験の問題・テキスト等を見て気になったメモです。
多分間違っているのであまり見ないで下さい。すみません。
（記載内容や参考にしたネット情報など問題がありましたら、早急に削除いたします。）
問題文など、「基本情報技術者試験ドットコム」様を参考・引用させていただくことがあります。感謝。）
********************************************************************
＜連結リストと二分探索木とヒープについて＞
●連結リスト（ここでは単方向リスト）は、１つのポインターを持たせる方法です。
連結リスト（単方向）
長所は、簡単にデータを追加できることです。（並び替え不要）
次のポインターを持たない配列に比べて、全体の構造を変えなくていい点です。
もしも、データを途中に挟みたい場合でも、１個後ろのポインターを変えるだけ。
例：A[1]の後ろに、A[4]を挟みたい時
A[1]の次のポインターとA[4]の次のポインターを入れ替えるだけ。
短所は、何番目のアレとかサーチしようとすると、次のポインターへ順に探索が必要なので時間がかかる。
（多分、線形探索で計算量ON）
●二分探索木は２つのポインターを持たせて、一番上の根よりも大きいか、小さいかで、
一段下に左右に配置していく方法です。
（1個のノードから最大２個ポインターを持たせるのでbinary tree）
関係ないかもしれないが、ソート済みのデータを検索する「二分探索法」（探索木ではない）
みたいに、上から何番目のアレを探そうとすると、たどっていける気がする。
（違うか？計算量は二分探索法のLog2Nなのか？？？）
長所は、連結リストと同じく、全体の構造を変えなくてもいいことだろう。
例：上記に１１を追加する場合、９の位置に入れることになる。（９は１段下げる）
上から、１１の入るところを探していくとこうなる。多分。（違うかも）
●ヒープについて、二分探索木に似ている。同じく１個のノードに対してポインターが２つのbinary tree。
（３本とかあるのか？）←あるようです。
ヒープは、一番上の根が一番小さい。
そこから下へ枝が延びていくが、１個上と１個下の節では、大小関係が
成立しているが、１左右の関係は大小関係なしに配置される。（上下の親子関係は成立）
（例：⑤と④は左右関係なし。多分、左から埋めるとか、規則を作るのだろう。）
（ちなみに二分探索木は左右は１個上との関係に左右された。）
ヒープは上から結構きれいに並んでいる。
ヒープはデータを整列させる仕組み（ソート）。
だから、ノードを追加する時、並べ替えが必要で、全体の位置が変わる場合がありうる。
最小値が変わる場合など。
（最小値を削除する場合など、処理は結構ややこしそうです。）
