ヒープ
挿入時と同様に、ルートに向かって入れ替え操作を繰り返す
なお削除前に正しいヒープ構造になっていれば、親要素 ≤ 子要素なので、両方が同時に成り立つことはない。
子は親より大きいか等しく、添字は 1 から開始するものとして記述する。また、木全体の要素数を N {\displaystyle N} とする。
操作対象の要素 n = N + 1 {\displaystyle n=N+1} とし、追加する要素を n {\displaystyle n} に置く。
要素 n {\displaystyle n} を親( n ÷ 2 {\displaystyle n\div 2} )と比較する。要素 n {\displaystyle n} がルート( n = 1 {\displaystyle n=1} )か、または比較結果が親以上なら終了。
親の方が大きければ親子を入れ替え、 n = n ÷ 2 {\displaystyle n=n\div 2} として繰り返す。