0

この質問はこれに似ています。違いは、 Min- Heapの代わりにバイナリの Max-Heapがあることです。これにより、質問がまったく異なります。

私の考え：

1) すべてのノードを調べて 2 番目に小さい要素を見つけます。これには O(n) かかります

2) 2 番目に小さい要素を見つけたら、その要素をバブルアップし、ルートに到達するまで親と交換します。これには O(logn) がかかります。

3）ルートから要素を削除し、最も右の要素を取得してルートの場所に保存します（通常のヒープ削除操作）。これにはO（logn）がかかります

合計は O(n) + O(logn) + O(logn) となり、これは O(n) です。

編集：バイナリを追加

それよりも良い解決策はありますか？

4

3 に答える 3

1

最小の 2 つの要素のコピーを保持するために、2 つの要素を持つ小さな配列を保持しないのはなぜですか?

次に、すべての操作は O(1) ステップで変更されるだけで、一定時間で答えを出すことができます。

于 2012-07-10T12:33:47.950 に答える
0

2 番目に小さい要素は、リーフまたはリーフの親であり、リーフはその唯一の子です。

2 番目に小さい要素を削除する方法:

  1. 葉を検索して見つけ、おそらく子供が 1 人しかいない父親を見つけます。の上）
  2. 2 番目に小さい要素がノードの親である場合、そのノードは最小の要素である必要があり、右端のリーフである必要があります。2 番目に小さいものをその子に置き換えて終了です。O(1)
    2 番目に小さい要素が葉の場合、それを最も深いレベルの右端の葉に置き換えてバブルアップします。O(ログ(n))

したがって、O(n)+O(log(n)) はまだ O(n) ですが、比較は少なくなります。

于 2012-05-09T15:32:49.350 に答える
0

ビッグ O 表記に関しては、いいえ、これ以上のことはできません。最大ヒープ内の任意の要素を見つけることはO(n).

ただし、トラバースする必要がある最大ノード数を減らすことができ1/2 * n、本質的にアルゴリズムの速度を 2 倍にすることができます。[まだO(n)ドメイン]、最大ヒープの 2 番目に小さい要素には最大で 1 つの sonがあるため、葉 (それらの n/2) のみをトラバースでき、息子が 1 つしかない最大で 1 つの要素をトラバースできます。(バイナリ ヒープは完全なツリーを表す配列であるため、多くても 1 つの要素にちょうど 1 つの息子があることに注意してください)。

除去ステップを少し強化することもできますが、それが重大な影響を与えるとは思えないため、私はわざわざそれに力を入れません.

于 2012-05-09T15:35:02.840 に答える