5

私は C++ でアプリケーションを作成しています。ここでは、プライオリティ キューに対して O(1) Dequeue 操作を行うことが重要ですが、Enqueue の複雑さはそれほど重要ではありません (もちろん n^2 または 2^n にならない限り) 。

最初は連結リストを使っていました。これはデキュー (O(1)) に非常に適していて、エンキューの複雑さも良好でした。唯一の問題は、それをソートすることでした。O（n）の複雑さで挿入ソートを使用すると、私のニーズに合ったという事実ではありません。しかし、リンクされたリストをソートするのは面倒です。ゆっくりでした。

ベクトルはまったくダメです。Dequeue は O(n) で、すべての要素を 1 つ後ろに移動します。エンキューはまだ O(n) ですが、はるかに高速です。

よりパフォーマンスの高い方法を提案できますか? ありがとう。

4

5 に答える 5

14

逆ソートvectorには O(1)pop_backと O( n ) の挿入があります。

于 2012-05-28T11:16:26.560 に答える
10

キューをソートされたリンクリストとして保存できます。フロントエレメントを取り外し、O(1)正しい位置にエレメントを挿入するのはですO(n)。

しかし、リンクリストの並べ替えは面倒です。遅いでした。

挿入するたびに完全な並べ替えを実行する必要はありません。あなたがしなければならないのは、（すでにソートされた）リストをトラバースして新しい要素の正しい位置を見つけ、そこに挿入することです。トラバーサルはO(n)であり、挿入はO(1)です。

于 2012-05-28T11:13:44.620 に答える
1

文献から実装する意思がある場合は、はるかに優れたソリューションがあります。

最悪の場合の複雑さ

削除: O(1)

削除分: O(1)

検索最小: O(1)

挿入: O(log n)

参照

MELDが線形時間をとることを許可されている場合、ディーツとラマンのフィンガー検索ツリーを使用することで、最悪の場合の定数時間でDELETE-MIN[3]をサポートできます。それらのデータ構造を使用することにより、 MAKEQUEUE、FINDMIN、DELETEMIN、DELETEは最悪の場合の時間 O(1) でサポートされ、INSERTは最悪の場合の時間 O(log n) で、MELDは最悪の場合の時間 O(n) でサポートされます。

Brodal、Gerth Stølting。「Fast Meldable プライオリティ キュー」。アルゴリズムとデータ構造に関する第 4 回国際ワークショップの議事録、282 ～ 290。WADS '95。ロンドン、英国、英国: Springer-Verlag、1995 年。

[3]:ディーツ、ポール F、ラジーヴ ラマン。「一定更新時間フィンガー検索ツリー」。情報処理レター52、いいえ。3 (1994): 147 – 154.

これは計算のRAM モデルを使用しますが：

私たちのデータ構造は、単位コストの尺度と対数ワード サイズのランダム アクセス マシン (RAM) モデルを使用します。

最近では、ポインター マシンモデルの計算内でのソリューションが提供されてい[1]ます。これには、O(1) の get-min、extract-min、get-max、extract-max、および O(log n) の挿入があります。

[1]: Brodal、Gerth Stølting、George Lagogiannis、Christos Makris、Athanasios Tsakalidis、Kostas Tsichlas。「ポインター マシンにおける最適なフィンガー サーチ ツリー」。Ｊ．コンピュータ．システム 科学。67、いいえ。2 (2003 年 9 月): 381–418。

于 2013-01-05T09:17:33.310 に答える
0

Boost には、優先キュー操作もサポートするヒープ データ構造のライブラリであるBoost.Heapが含まれるようになりました。このページには、提供された各データ構造のコア操作の償却された複雑さの表があります。フィボナッチ ヒープの特徴: O(1) プッシュ、O(log(N)) ポップ、O(1) 増加、および (必要な場合) O(log(N)) 減少。

于 2012-05-28T11:35:29.673 に答える
0

バランス型二分探索木と連結リストを組み合わせることができます。ツリーの各要素には、その子へのリンクと、次の前の要素へのリンクがあります。次に、次のことができます。

O(lg n) 挿入、削除、検索。O(1) - 最小値と最大値を抽出

別の可能性は、ランダム化された構造を使用してもかまわない場合は、skiplist を使用することです。あなたも持っているより:

O(lg n) 挿入、削除、検索。O(1) - 最小値と最大値を抽出

于 2012-05-28T12:05:34.690 に答える