Speical minHeap は、各レベルが左から右にソートされる minHeap です。最悪の場合 、すべてのn要素を順番に印刷するにはどうすればよいですか?O(n)
minHeap は、ツリーが完全なバイナリ ツリーであるバイナリ ヒープによって実装されます (図を参照)。
特別な minHeap の例を次に示します。
したがって、結果は次のようになります。[1,3,4,5,8,10,17,18,20,22,25,30]
宿題からの質問。
2 に答える
2
がヒープのサイズに依存しないパラメーターである場合n、標準的な比較ベースのモデルでは、これは不可能です。あなたが言及したよりも既存の順序や、ヒープのすべての要素が十分に低い境界の下の整数であるなど、追加の制限が必要になります。
height のヒープがkあり、ルートとその左側の子のチェーンの値が 1、2、3、... k であるとします。「特別な最小ヒープ」条件に違反することなく、これらのノードの k-1 個の右側の子に >k の値を任意の順序で割り当てることができます。次に、それらよりも大きい値を割り当てて、残りのヒープを埋めます。このヒープの上位 2k-1 値を出力するには、任意の順序である可能性がある k-1 値を並べ替える必要があります。これは、比較を短時間で行うことはできませんO(k*log(k))。
がヒープのサイズであると想定される場合n、これは簡単です。ヒープ不変条件は不要です。レイヤーがソートされていることだけが重要です。1 番目と 2 番目のレイヤーをマージしてから、連続する各レイヤーを既にマージされた結果にマージするマージソートには、O(n) 時間がかかります。k 番目のマージは、2^k-1 個の既にマージされた要素を次のレイヤーの <=2^k 要素とマージし、O(2^k) 時間かかります。O(log(n)) 個のマージがあり、k=1 から k=log(n) までの O(2^k) を合計すると O(n) が得られます。
于 2016-03-08T19:10:23.550 に答える