━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━ データ構造・アルゴリズム論 確認問題６ ━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
●問 (ヒープの基本操作) 2分木で表した次のヒープについて考える． ２ ／＼ ４ ６ ／ ８ このヒープに対して，次の基本操作を(授業で解説されたアルゴリズムで)順に実行する． 0を挿入，削除，10を挿入，削除，削除． 基本操作ごとのヒープの変化を，2分木を使って図示せよ． ────────────────────────────────────── ●答 (ヒープの基本操作) ２ → ０ → ２ → ２ → ４ → ６ ／＼ ／＼ ／＼ ／＼ ／＼ ／＼ ４ ６ ２ ６ ４ ６ ４ ６ ８ ６ ８ 10 ／ ／＼ ／ ／＼ ／ ８ ８ ４ ８ ８ 10 10 [解説] ヒープとは，ヒープ条件 (どの親もその子以下) を満たす完全2分木である． ヒープに値を挿入するには，最下段に左詰めで葉を追加し，葉から根へ向けて ヒープ条件を満たさない (親＞子 が成り立つ) 親子の値を交換する． ヒープから値を削除するには，最下段の最右の値を根に移し，根から葉へ向けて ヒープ条件を満たさない (親＞子 が成り立つ) 親子の値を交換する． ただし，親が左右両方の子より大きいなら，ヒープ条件を満たすようにするには， 子の小さい方と親の値を交換する． 値の交換は親子の間だけで起こり，子の間では起こらないことに注意する． ━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━ 授業のホームページ 山田 俊行 https://www.cs.info.mie-u.ac.jp/~toshi/