next up previous contents index
: ヒープの配列による表現 : ヒープソート : ヒープソート   目次   索引

ヒープ

次の性質を満たす図を考える (図 14.1). これを2 分木とよぶ.

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

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

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

  4. 各ノードには数字が書かれていて, 親は子より小さくない.
このような性質を満たす図をヒープと呼ぶ.

図 14.1: ヒープの例
\begin{figure}
\setlength{\unitlength}{1cm}
\begin{picture}(24,6)(0,0)
\put(7,4...
...\put(6,0){ \underline{6} }
\put(8,0){ \underline{2} }
\end{picture}
\end{figure}

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

方法 2 の利点は

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



Nobuki Takayama 平成15年9月12日