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

Question

ソートされた配列に裏打ちされた最小バイナリヒープとして優先キューを実装しようとしています。update_key関数を対数時間で実行しようとしていますが、これを行うには、配列内のアイテムの位置を知る必要があります。マップを使用せずにこれを行う方法はありますか？もしそうなら、どのように？ありがとうございました

Answer 1

任意の要素のキーを本当に変更できるようにしたい場合、ヒープはデータ構造の最良の選択ではありません。それがあなたに与えるのは、次の組み合わせです。

1. コンパクトな表現 (ポインターなし、配列と暗黙のインデックス スキームのみ)
2. 対数挿入、リバランス
3. 最小 (最大) 要素の対数除去。
4. 最小 (最大) 要素の値への O(1) アクセス。-

1. の副次的な利点は、ポインターがないため、malloc/free( new/delete) の呼び出しが大幅に少なくなることです。マップ (標準ライブラリではバランスの取れたバイナリ ツリーとして表されます) は、これらの中間の 2 つを提供し、

1. find()任意のキーで 対数。

mapしたがって、別のデータ構造をヒープにアタッチし、ポインターをヒープに格納してから、ポインターを介して比較演算子を逆参照することはできますが、最初にa を使用するだけで時間と空間が複雑になることにすぐに気付くでしょう。.

Answer 2

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

これらの仮定が正しい場合は、これを試してください: 1) ヒープ内の項目を見つけます (IE: ソートされた配列であるため、バイナリ検索)。2）キーを更新します（値を変更するだけで、一定の時間です）3）ヒープログ（n）からアイテムを削除して再ヒープします。
4) アイテムをヒープ ログ (n) に挿入します。

したがって、log(n) + 1 + log(n) + log(n) となり、log(n) になります。

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

Answer 3

これが配列ベースのヒープのトレードオフです。優れたメモリ使用量 (良好な局所性と最小限のオーバーヘッド) が得られますが、要素を追跡できなくなります。それを解決するには、いくらかのオーバーヘッドを追加する必要があります。

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

Update_key (および任意の要素の削除) は、( を介してheap_index) 要素を見つけるのに一定の時間がかかり、正しい位置にバブリングするのに log(n) 時間がかかるため、log(n) 時間です。