14

私はインタビューで尋ねられました：

最大ヒープから最小要素を取得する際の最良の時間計算量はどれくらいですか？

ヒープサイズが既知であり、ヒープが配列を使用してバイナリヒープとして実装されていると仮定して、O（1）として応答しました。このように、私の仮定によれば、最小値はにありheap_array[heap_size]ます。

私の質問は、この答えが正しければということです。そうでない場合、正解は何ですか？

4

6 に答える 6

35

私の質問は、この答えが正しければということです。

いいえ、それは正しくありません。唯一の保証は、各ノードにその下のサブツリーの最大要素が含まれていることです。つまり、最小要素はツリー内の任意の葉にすることができます。

そうでない場合、正解は何ですか？

正解はO（n）です。各ステップで、最小要素を検索するために、左と右の両方のサブツリーをトラバースする必要があります。事実上、これは最小値を見つけるためにすべての要素をトラバースする必要があることを意味します。

于 2012-07-25T07:52:06.060 に答える
11

最高の複雑さはO(n)です。スケッチプルーフ：

  • 最小要素は、絶対的に最下位レベルのノードのいずれかである可能性があります（実際には、最下位レベルにすることもできませんが、これらから始めましょう）。
  • n/2最下位レベルのノードまで存在する可能性があります。
  • あなたが探しているものはあなたが最後に見た場所にあるかもしれないので、それらすべてを調べる必要があります。それらのうちの1つを除くすべてを調べても、最後のものが最小であるかどうかはわかりません。
  • したがって、Omega(n)検査が必要です。

O(n)配列がヒープであるという事実を無視することで明らかにそれを実行できるため、境界は厳しくなります。

道徳：それはおそらくヒープと呼ばれます。なぜなら（寝室の床にある衣服のヒープと同様に）、一番上に着くのは簡単で、残りの部分に着くのは難しいからです。

于 2012-07-25T07:57:21.830 に答える
1

最大ヒープからの最小要素：

  1. 最後のレベルで検索=O（n / 2）= O（n）

  2. 検索された要素を最後の要素に置き換え、ヒープサイズを1 = O（1）減らします

  3. 置き換えられた要素にMaxheapifyを適用する=O（log n）

合計時間=O（n）+ O（1）+ O（log n）= O（n）

于 2015-11-21T07:22:39.827 に答える
1

MINIMUM_ELEMENT->最大ヒープの場合はO（n）時間、最小ヒープの場合はO（1）時間がかかります。MAXIMUM_ELEMENT->最大ヒープの場合はO（1）時間、最小ヒープの場合はO（n）時間がかかります。

于 2017-07-11T07:31:59.310 に答える
0

正解はO（n）1）最大ヒープから最小要素を見つけるn番目のmax（最小要素に他なりません）を見つけます。これはn（n-1）/2の比較を行います==O（n ^ 2）2）最初にまったく配列です。最小要素を見つけるには、選択ソートの最初のパスを適用します。これにはO（n）時間がかかります。3）最大ヒープ内のn個の要素を1つずつ削除します（これは検索のみです）。これにはO（nlogn）時間がかかります。3つの方法の中で最良のものはO（n）です。したがって、正解はO（n）時間になります

于 2019-06-30T18:19:13.833 に答える
0

最も複雑なのはO（n）です。

それについてはあまり書かれていませんが、 MAX-heap
のmin要素とmin-heapのMAX要素 も（最低レベル-1）であり、常に最低レベルであるとは限りません。

説明：
ヒープには、最下位レベルの右側からノードが欠落するオプションがあるため、バランスの取れた（完全な）ツリーではない可能性があります。これにより、（下位レベル-1）にもリーフが含まれるようになります。

これは、チェックするn/2があることを意味します。したがって、大きなO項では、 O（n）に等しくなります。

そのような状況の例：

  • MAX-heap [10,9,1,8,7]（1は小さい値ですが、最低レベルでは表示されませんでした）
  • min-heap [8,10,20,17,15]（20は最大値ですが、最低レベルでは表示されませんでした）
于 2019-07-16T11:13:38.500 に答える