0

簡単な証明へのアプローチを理解/取得しようとするあなたの助けが必要です。

n個の異なる要素を持つ最大ヒープが与えられ、xがディープDのヒープ内の要素（ヒープを表すツリー内）であるとします。ここで、一連のDeleteMax操作を実行していると仮定します。

  1. xがヒープから抽出されるまでに実行する必要のあるDeleteMax操作の最大数はいくつですか。

  2. xがヒープから抽出されるまでに実行する必要のあるDeleteMax操作の最小数はいくつですか。

ノート：

xとその親がヒープ内で最大の要素である場合、xはD + 1 DeleteMax操作の後に抽出されることを指定することで2番目の要素を証明できたと思います（そのうちのDは彼の親の抽出専用です）。

最初の方法がうまくいかないことがわかりました。正しく証明するためにどのアプローチを使用する必要があるのか​​わかりません。

4

1 に答える 1

2

私はあなたが正しいと思います。2番目のケースは、xの親と祖父母だけがxより大きい場合に発生しますが、いとこ、叔父などは発生しません...ルートに直線上の前任者のみが発生します。

最初のケースは、xの子のみがxよりも小さい場合に発生します。したがって、ヒープの高さがHの場合、最大値は、高さHの完全なヒープから高さHDの完全なヒープを引いたものになります。

于 2013-02-06T04:44:40.150 に答える