6

私は現在この論文を読んでおり、5ページで、一般的な知識と見なされるバイナリヒープのプロパティについて説明しています。しかし、彼らの指摘の1つは、私がこれまで見たことがなく、理解できないことです。著者は、バランスの取れたバイナリヒープが与えられた場合、標準の幅優先探索を使用して、そのヒープの要素を要素ごとのO（log n）時間でソートされた順序で一覧表示できると主張しています。元の文言は次のとおりです。

バランスの取れたヒープでは、新しい要素を対数時間で挿入できます。幅優先探索を使用するだけで、ヒープの要素を重み順に一覧表示できます。対数の時間をかけて各要素を生成します。

著者がこれによって何を意味するのかわかりません。「幅優先探索」と言うときに最初に頭に浮かぶのは、ルートから始まるツリー要素の幅優先探索ですが、要素を並べ替えた順序で一覧表示することは保証されておらず、対数時間もかかりません。要素ごと。たとえば、この最小ヒープでBFSを実行すると、関係をどのように解除しても、要素が順不同で生成されます。

             1
            / \
          10   100
         /  \
        11  12

これは常に11または12の前に100をリストしますが、これは明らかに間違っています。

私は何かが足りないのですか？ヒープ上で実行して、それぞれの対数時間を使用して要素をソートされた順序で取得できる、単純な幅優先探索はありますか？明らかに、毎回最小要素を削除してヒープを破壊的に変更することでこれを行うことができますが、作成者の意図は、これを非破壊的に行うことができるように思われることです。

4

2 に答える 2

5

優先キュー（別のヒープが必要です！）を使用してヒープをトラバースすることにより、要素をソートされた順序で取得できます。これが彼が「幅優先探索」と呼んでいるものだと思います。

（アルゴリズムの担当者が与えられれば）それを理解できるはずですが、基本的に優先キューの鍵はノードの重みです。ヒープのルートを優先キューにプッシュします。それで：

while pq isn't empty
    pop off pq
    append to output list (the sorted elements)
    push children (if any) onto pq

これが彼の言っていることなのか（全然）よくわかりませんが、漠然と説明に合っていて、あまり活動がなかったので、出してみたほうがいいと思いました。

于 2011-08-28T11:59:55.933 に答える
0

100未満のすべての要素が左側にあることがわかっている場合は、左側に移動できますが、いずれの場合でも、100に達しても、左側に要素がないことがわかるので、外に出ます。いずれにせよ、検索している要素がないことに気付く前に、最悪の場合2回ノード（または他のノード）から移動します。あなたがこの木に入るのは男性よりも多くても2*log（N）回です。これは、log（N）の複雑さに単純化されます。

ポイントは、「ねじ込み」して「間違った」ノードに移動したとしても、最悪の場合、そのノードに一度移動するということです。

編集
これは、ヒープソートがどのように機能するかを示しています。最上位の要素を取り出すたびに、N（log n）の複雑さを使用してヒープを再構築する必要があることを想像できます。

于 2011-08-27T01:00:09.393 に答える