O(n log n) 未満の最悪の場合の複雑さ、つまり n 個の連続した挿入を使用して、指定された n 個の要素を持つ二項ヒープを最初に構築する方法はありますか? (挿入の償却コストが O(1) であることはわかっているため、ビルドの平均時間の複雑さは小さくなります。) バイナリ ヒープの場合、n 個の要素すべてをバイナリ ツリーに入れ、heapify/siftDown を実行する、より効率的なビルド実装があります。要素の前半を逆順で。疑問に思っているのは、二項ヒープに対して同様に賢いものが存在するかどうかです。
質問する
924 次
1 に答える
2
実際には、n 個の値をすべてヒープに挿入するのにかかる時間は O(n) だけです。二項ヒープ挿入の最悪の場合の実行時間は O(log n) ですが、平均ではそれよりも低くなります。
これは、償却分析を使用してこれを確認する 1 つの方法です。二項ヒープ内の各ツリーに 1 クレジットを置きます。挿入を行うたびに、k 個の異なるツリーをマージする場合、実際の実行時間は Θ(1 + k) です。また、これを行う過程で k クレジットを消費します。マージされたツリーごとに 1 つなので、償却コストは O(1) です。したがって、間に削除がないと仮定すると、空の二項ヒープへの一連の n 個の挿入には、O(n) の時間がかかります。これは、バイナリ ヒープとは異なり、事前に要素数 n がわからない場合でも機能します。
または、遅延二項ヒープを使用することもできます。この場合、挿入には最悪の場合の時間が O(1) かかり、削除には O(log n) が償却されます。その場合、一連の n 回の挿入にも O(n) 時間かかります。
お役に立てれば！
于 2014-06-10T21:59:14.443 に答える