ヒープ

次の性質を満たす図 (2 分木) を考える.

1. 各レベル ($i=0,1,\ldots$) には, 最終レベルを除いて $2^i$ 個の元 (ノード) が並んでいる.

2. 最終レベルは左からすき間なしに並んでいる.

3. レベル $i$ の左から $k$ 番目のノードは, レベル $i+1$ の左から $2k-1$, $2k$ 番目のノードと線で結ばれている. (存在すればの話) 線で結ば れているノードの組において, 上 (レベル番号が小さい) を 親, 下を 子と呼ぶ. レベル 0 のノードを 根, 子がないノードを 葉 と呼ぶ.

4. 各ノードには数字が書かれていて, 親は子より小さくない.

このような性質を満たす図を ヒープと呼ぶ.

図 1: ヒープの例

与えられた集合からヒープを構成できれば, 元の集合を整列するのは 容易である.

• 方法 1
  1. レベル 0 のノードが最大なので, これを取り外す.
  2. 2 番目に大きいのはレベル 1 の 2 つのうちどちらか. 大きい方を レベル 0 に昇格.
  3. レベル 1 の空いた場所に, レベル 2 から昇格, $\ldots$
  4. これらを繰り返す.

• 方法 2
  1. レベル 0 のノードが最大なので, これを取り外す.
  2. 最終レベルの右端のノードをとりあえずレベル 0 に置く. 2 分木を構成するノードの個数は 1 減っている.
  3. ヒープ条件が満たされるまで, レベル 0 に置いた元を順に落して行く.

方法 2 の利点は

• 「ある場所から落す」というサブルーチンが, ヒープを構成するのに そのまま使える.

• 最終レベルの右端が空くので, そこに取り外したレベル 0 の元を置ける. すると, 最終的にヒープ自体を上位レベルから並べて見ると, 整列されて いることになる.

「落す」とは, (親, 子1, 子2) という組がヒープ条件を満たす ように入れ換えることである. 入れ換えの必要がなくなった時点で ストップして次のステップに進めばよい.