C++任意の要素メソッドを削除したヒープ

Question

私は自分のヒープを実装する方法を任意の数（最小または最大）だけでなく、削除するが、私は1つの問題を解決できません。その削除関数を書くには、ヒープ内の要素へのポインタが必要です（指定された要素を削除するO（logn）の時間を持つために）。しかし、私はこのようにしようとした：

vector<int*> ptr(n); 

それはもちろん動作しませんでした。

intを含む別のクラスまたは構造体をヒープに挿入する必要があるかもしれませんが、今はint型のソリューションを探したいと思います（既にint型を実装しているためです）。

Answer 1

ルート以外のオブジェクトを削除（または優先度を変更）する必要がある場合、dヒープは必ずしも理想的なデータ構造ではありません。ノードはその位置を変えず、さまざまな動きを追跡する必要があります。しかし、それは可能です。このようなヒープを使用するには、新規に挿入されたオブジェクトへのハンドルを返します。このハンドルは、置かれている何らかのノードを識別します。 dヒープアルゴリズムはツリーが完璧にバランスの取れたツリーであるため、実際には配列を使用してツリーを実装する必要があります。これらの2つの要件（配列を使用し、ノードを置いたままにする）は相互排他的なので、両方を実行し、ノードから配列へのインデックスを持たなければなりません（配列内のオブジェクトの位置を見つけることができます）ノードへの配列（位置が変わったときにノードを更新できるように）ほとんどの場合、ノードを多く動かすことは望ましくありません。つまり、複数のノードを検索することによってノードを移動する正しい方向を見つけることができます。つまり、広告> 2を使用します。

本質的にノードベースのヒープです。特に、特定の使用パターンに対して得られるフィボナッチヒープは、通常のO（ln（n））の複雑さよりもより償却された複雑さを有する。ただし、ノードの優先度を頻繁に変更する必要がある場合や、データセットがかなり大きい場合は、実装するのがいくらか難しく、実際の効率はほんのわずかです。

Answer 2

ヒープは、特定の種類のデータ構造です。要素は2分木に格納され、要素を追加または削除するための十分に確立された手順があります。多くの実装では、ツリーノードを保持する配列を使用し、log（n）要素を移動する要素を削除します。アレイが使用される通常の方法では、アレイ位置nのノードの子は、位置2nおよび2n + 1に格納されます。要素0は空のままです。

This Wikipedia pageアルゴリズムを説明してくれてうまくいきます。