ヒープからルートの削除
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/01/03 14:40 UTC 版)
「二分ヒープ」の記事における「ヒープからルートの削除」の解説
ヒープからルートを削除する手順、つまり効果的に最大ヒープ内で最大要素を検索したり最小ヒープから最小要素を検索する手順は、up-heap とよく似ている。これを down-heap (bubble-down, percolate-down, sift-down, trickle down, heapify-down, cascade-down) と呼ぶ。ルートを削除するということは、ルートを木の末端の要素と入れ替えることである。前と同じ最大ヒープを例にとると、 「11」を削除して「4」と入れ替える。 親である「4」は子である「8」よりも小さいのでヒープの制約条件に違反している。この2つの要素を交換すればヒープの制約条件は保たれ(「4」はより大きい子と交換される。最小ヒープならばより小さい子と交換される)、これ以上操作の必要はない。
※この「ヒープからルートの削除」の解説は、「二分ヒープ」の解説の一部です。
「ヒープからルートの削除」を含む「二分ヒープ」の記事については、「二分ヒープ」の概要を参照ください。
ウィキペディア小見出し辞書の「ヒープからルートの削除」の項目はプログラムで機械的に意味や本文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。
お問い合わせ。
- ヒープからルートの削除のページへのリンク
