Updated at: 2014-12-06
Data Structure
Heap
- ヒープ - Wikipedia
- 最大値（or 最小値）を求めるのに適した木構造
- 最大ヒープなら、ヒープの性質 (heap property) は「親ノードは子ノードより常に大きいか等しい」
- 優先度付きキュー (priority queue) の実装としてよく用いられる
- 任意の順序で入力されるデータ群から、最大（最小）のものを順に取り出すという操作が高速にできる
- イベントキューとかの実装に向いてるね
- 二項ヒープ、フィボナッチヒープなど、バリエーションがたくさんある
Skip List
- 順序つきの Link List を階層的に持つことで探索を速くする
- 上の階層ほど要素が歯抜けになってる感じ
- 最下層は全部の要素が入っていて、i の層の要素は i + 1 の層では p ％で存在
- p の値を変えれば探索時間とメモリ使用量のトレードオフがとれる
- 最下層が各駅停車だとすると、上の層に上がるにつれて快速、急行、特急になってくイメージ
- 乱択アルゴリズム を用いることで 平衡 2 分探索木 と同等の効率を得ているわけだね
