名古屋大学情報学研究科複雑系科学専攻 2019年8月実施情3

标签：

Author

祭音Myyura

Description

ヒープは木構造の1つで、完全2分木により表現される。木の根である節の番号を1とし、節の数が増えるに応じて、2、3、…と順に節に番号を割り振る。各節は値を持つ。ここでは、親の節の値が子の節の値以下となっているヒープ（最小ヒープ）を考える。

[1] 以下の配列をヒープの木構造として図示する場合、アからエに対応する節番号を示せ。

節番号	1	2	3	4	5	6
値	794	1333	1582	1467	1868	1603

          ア
        /    \
      イ      1582（節3）
     /  \       /
   ウ  1868（節5） エ

[2] 完全2分木の親と子の節の番号の関係について説明せよ。

[3] 値として645をもつ節を、[1]で図示したヒープの木構造での節番号3の右下に追加する場合、節を入れ替えてヒープを再構成する過程の2分木の変化を図示せよ。

[4] [3]で作成したヒープから値として645をもつ節を削除した場合に、節を入れ替えてヒープを再構成する過程における2分木の変化を図示せよ。

[5] [1]で作成したヒープを用いて、値を昇順にソートする。ソートの方針を1文で述べた上で、ソートする過程における2分木の変化を図示せよ。

[6] $n$ 個の節からなるヒープを再構成する場合の最悪の計算量を示せ。また、その理由を述べよ。

[7] 優先度つき待ち行列とは、優先度の高いものから取り出すことができる待ち行列である。優先度つき待ち行列を実装する場合にヒープを利用する方法を述べよ。

Kai

以下、配列は節番号順に記し、配列の先頭を節番号1とする。

[1]

完全2分木では節番号順に上から左詰めで配置されるので、

\boxed{\text{ア}=1,\quad \text{イ}=2,\quad \text{ウ}=4,\quad \text{エ}=6}

である。

[2]

節番号を $i$ とすると、存在する場合、

左の子： $2i$
右の子： $2i+1$
親（ $i\ge 2$ ）： $\left\lfloor i/2\right\rfloor$

である。したがって、偶数番号の節は左の子、1以外の奇数番号の節は右の子である。

[3]

節番号3の右の子は節番号 $2\cdot3+1=7$ である。645を節7に追加し、親より小さい間、親と交換する。

追加直後
          794
       /       \
    1333       1582
   /   \       /   \
1467  1868  1603   645

節7と節3を交換する。

          794
       /       \
    1333        645
   /   \       /   \
1467  1868  1603  1582

さらに節3と節1を交換する。

          645
       /       \
    1333        794
   /   \       /   \
1467  1868  1603  1582

配列では、

[794, 1333, 1582, 1467, 1868, 1603, 645]
→ [794, 1333, 645, 1467, 1868, 1603, 1582]
→ [645, 1333, 794, 1467, 1868, 1603, 1582]

となる。

[4]

645は根にある。完全2分木を保つため、末尾の節7の値1582を根へ移し、節7を削除する。

          1582
       /        \
    1333         794
   /   \         /
1467  1868     1603

根の二つの子のうち小さい値794と交換する。

          794
       /       \
    1333       1582
   /   \        /
1467  1868    1603

節3では $1582 \le 1603$ なので終了する。配列では、

[1582, 1333, 794, 1467, 1868, 1603]
→ [794, 1333, 1582, 1467, 1868, 1603]

となる。

[5]

方針：根の最小値を取り出して出力列の末尾へ追加し、末尾要素を根へ移して下向きに再ヒープ化する操作を、ヒープが空になるまで繰り返す。

初期ヒープは次である。

          794
       /       \
    1333       1582
   /   \        /
1467  1868    1603

794を取り出す

[1603, 1333, 1582, 1467, 1868]
→ [1333, 1603, 1582, 1467, 1868]
→ [1333, 1467, 1582, 1603, 1868]

          1333
       /        \
    1467        1582
   /   \
1603  1868

出力列：[794]

1333を取り出す

[1868, 1467, 1582, 1603]
→ [1467, 1868, 1582, 1603]
→ [1467, 1603, 1582, 1868]

        1467
       /    \
    1603    1582
   /
1868

出力列：[794, 1333]

1467を取り出す

[1868, 1603, 1582]
→ [1582, 1603, 1868]

      1582
     /    \
  1603   1868

出力列：[794, 1333, 1467]

1582を取り出す

[1868, 1603]
→ [1603, 1868]

    1603
   /
1868

出力列：[794, 1333, 1467, 1582]

残りを取り出す

1603を取り出す： [1868]
1868を取り出す： []

したがって、昇順の結果は

\boxed{794,\ 1333,\ 1467,\ 1582,\ 1603,\ 1868}

である。

[6]

[3]、[4]のような1回の挿入または削除後の再ヒープ化の最悪計算量は、

\boxed{\Theta(\log n)}

である。 $n$ 節の完全2分木の高さは $\lfloor\log_2 n\rfloor$ であり、交換は根から葉まで、または葉から根までの1本の経路上で高々高さ回だけ行われるからである。各段での比較・交換は定数時間である。

なお、[5]のヒープソート全体ではこの削除を $n$ 回行うため、最悪計算量は $\Theta(n\log n)$ となる。

[7]

優先度をキーとしてヒープに格納する。本問の最小ヒープを使う場合は、小さいキーほど高優先度と定める。

挿入：新要素を完全2分木の末尾へ置き、親より小さい間は上向きに交換する。
最高優先度要素の参照：根を見るだけなので $O(1)$ 。
取り出し：根を取り出し、末尾要素を根へ移した後、小さい子と下向きに交換する。

挿入と取り出しはともに $O(\log n)$ である。数値が大きいほど高優先度とする場合は、最大ヒープを用いるか、キーの符号を反転すればよい。

Author​

Description​

Kai​

[1]​

[2]​

[3]​

[4]​

[5]​

794を取り出す​

1333を取り出す​

1467を取り出す​

1582を取り出す​

残りを取り出す​

[6]​

[7]​