2011-12-05 珠玉のプログラミング コラム14 ヒープ

* ヒープとは

二分木のデータ構造であり、次の二つの性質を持つ。

「ヒープの順序」: 親ノードは必ず子ノードより小さいか等しい（または大きいか等しい）。
「ヒープの形」: バランスがかけているのは右下のみ。

これは配列Aで表現するのに都合がいい。
つまりA[0] をルートノードとし、A[1],A[2] をその子ノード、A[3..6]を孫ノード、とする。

すなわち ∀2

* 二つの重要な関数

shiftup() と shiftdown()

* ヒープソートと優先度つきキューが実現できる。

* ヒープソートの計算量

平均 nlogn、最悪も nlogn