優先度キュー - バイナリヒープ

ソートされた配列にバックアップされた最小バイナリヒープとして優先度キューを実装しようとしています。私は対数時間で実行するupdate_key関数を取得しようとしているが、これを行うには、配列内の項目の位置を知る必要があります。とにかくマップを使わなければこれをすることはありますか？もしそうなら、どうですか？ありがとう優先度キュー - バイナリヒープ

出典

2012-04-15 Richard

update_key関数とは何ですか？ – DRVic

バイナリヒープにキー、要素のペアが含まれているため、要素のキーを更新する関数 – Richard

あなたのfindキー関数はlog（n）時間で動作するはずです。あなたの更新（キーの変更）は一定の時間でなければなりません。あなたの削除関数はlog（n）の時間に実行する必要があります。あなたの挿入関数はlog（n）時間でなければなりません。

これらの前提条件が当てはまる場合は、 1）ヒープ内の項目を探します（ソートされた配列であるため、IE：バイナリ検索）。 2）キーを更新してください（値を変更するだけです、一定時間です） 3）ヒープログ（n）から項目を削除して、再度ヒープログを作成してください。
4）ヒープログにアイテムを挿入します（n）。

したがって、log（n）+ 1 + log（n）+ log（n）はlog（n）になります。

注：オーバーヘッドを追加する配列などを再割り当てする必要がある場合、これは償却されます。とにかくそれを頻繁に行うべきではありません。

出典

2012-04-15 03:45:54

ソートされた配列を意味するとは思わない。典型的なバイナリヒープ実装では配列内の要素は保持されますが、ヒーププロパティのみがtrueである必要があります。すべての要素をソートしたままにして、要素を挿入したり削除したりするのにO（log（n））の複雑さが残っているとは思えません。 –

これは意味があります。実際のヒープ構造を使用すると仮定すると、ヒープのルートノードは2つの子よりも（並べ替えの点で）良くなければならず、各子は別のヒープのルートとみなされ、これは再帰的に適用されます。私は昨晩私の心を邪魔しなかった理由は分かりません。説明をありがとう。 –

これはアレイバックのヒープのトレードオフです。優れたメモリ使用率（良好なローカリティと最小のオーバーヘッド）が得られますが、要素の追跡は失われます。これを解決するには、いくつかのオーバーヘッドを追加する必要があります。

解決策の1つはこれです。ヒープには、タイプC*のオブジェクトが含まれています。 Cは、intメンバheap_indexを持つクラスで、ヒープ配列内のオブジェクトのインデックスです。ヒープ配列内の要素を移動するときは常に、その要素を新しいインデックスに設定するためにheap_indexを更新する必要があります。

Update_key（任意の要素の削除と同様に）はlog（n）時間であり、要素を見つけるために（heap_indexを介して）一定の時間がかかり、log（n）時間だけ正しい位置にバブルする。

出典

2012-04-15 05:10:08

実際に任意の要素のキーを変更できるようにするには、ヒープがデータ構造の最良の選択ではありません。

コンパクトな表現（なしポインタ、単にアレイと暗黙のインデックススキーム）
対数挿入、リバランス最小（最大）の要素の
対数除去：何それはあなたを与えることの組み合わせです。
O（1）最小（最大）の要素の値へのアクセス。 -

ポインタの欠如は、malloc/free（new/delete）への呼び出しが実質的に少ないことを意味します。（バランスの取れたバイナリツリーなどの標準ライブラリで表される）マップは、任意のキーに

対数find()に追加して、あなたにこれらの真ん中の2つを提供します。

ヒープに別のデータ構造を添付し、ヒープにポインタを格納してから、比較演算子を参照してポインタを逆参照できるようになりましたが、ちょうど時間と空間の複雑さ最初はmapを使用しています。

出典

2012-04-16 11:29:10 DRVic

優先度キュー - バイナリヒープ

答えて

関連する問題