: ヒープの配列による表現
: ヒープソート
: ヒープソート
目次
索引
次の性質を満たす図を考える (図 14.1).
これを2 分木とよぶ.
- 各レベル (
) には, 最終レベルを除いて
個の元
(ノード) が並んでいる.
- 最終レベルは左からすき間なしに並んでいる.
- レベル
の左から
番目のノードは, レベル
の左から
,
番目のノードと線で結ばれている. (存在すればの話) 線で結ば
れているノードの組において, 上 (レベル番号が小さい) を親, 下を
子と呼ぶ. レベル 0 のノードを根, 子がないノードを葉
と呼ぶ.
- 各ノードには数字が書かれていて, 親は子より小さくない.
このような性質を満たす図をヒープと呼ぶ.
図 14.1:
ヒープの例
 |
与えられた集合からヒープを構成できれば, 元の集合を整列するのは
容易である.
- 方法 1
- レベル 0 のノードが最大なので, これを取り外す.
- 2 番目に大きいのはレベル 1 の 2 つのうちどちらか. 大きい方を
レベル 0 に昇格.
- レベル 1 の空いた場所に, レベル 2 から昇格,
- これらを繰り返す.
- 方法 2
- レベル 0 のノードが最大なので, これを取り外す.
- 最終レベルの右端のノードをとりあえずレベル 0 に置く.
2 分木を構成するノードの個数は 1 減っている.
- ヒープ条件が満たされるまで, レベル 0 に置いた元を順に落して行く.
方法 2 の利点は
- 「ある場所から落す」というサブルーチンが, ヒープを構成するのに
そのまま使える.
- 最終レベルの右端が空くので, そこに取り外したレベル 0 の元を置ける.
すると, 最終的にヒープ自体を上位レベルから並べて見ると, 整列されて
いることになる.
「落す」とは, (親, 子1, 子2) という組がヒープ条件を満たす
ように入れ換えることである. 入れ換えの必要がなくなった時点で
ストップして次のステップに進めばよい.
Nobuki Takayama
平成15年9月12日