ヒープ
ヒープ構造では子要素間の大小関係に制約がないため、目的とする要素が見つかるまで全要素を順に調べる必要がある。したがって、任意のデータを探索する必要がある場合にヒープ構造を使うことは勧められない。
ただし、ルートに最小(または最大)の要素が来ることは保証されている。これを利用してソートを行うアルゴリズムがヒープソートである。
子は親より大きいか等しく、添字は 1 から開始するものとして記述する。また、木全体の要素数を N {\displaystyle N} とする。 ルートを削除する手順は以下のとおりである。
操作対象の要素 n = 1 {\displaystyle n=1} とし、要素 N {\displaystyle N} を 1(ルート)に移動する。
要素 n {\displaystyle n} を子( 2 n {\displaystyle 2n} および 2 n + 1 {\displaystyle 2n+1} )と比較する。子が存在しない( 2 n > N {\displaystyle 2n>N} )か、またはすべての子の比較結果が要素 n {\displaystyle n} 以上なら終了。
小さいほうの子と要素 n {\displaystyle n} を入れ替え、 n {\displaystyle n} を入れ替えた子の添字として繰り返す。
ルート以外を削除する場合も、要素 N {\displaystyle N} を削除箇所に移動するところまでは同じである。 ただし、その後の操作は以下の条件分岐が必要になる。