3

「エンキュー」、「デキュー」、「最小」、「最大」を含むキューのようなデータ構造を設計できますか? 2 つのスタックを使用してキューを作成し、最小値と最大値をそれぞれ見つける方法は知っていますが、両方を同時に取得するにはどうすればよいですか?

ありがとう

4

4 に答える 4

3

標準のコンテナを使用すると、のような完全に順序付けられたデータ構造は、とを使用するなどstd::set、両方の極値へのアクセスを提供します。同じ優先度のオブジェクトが複数ある場合は、任意の方法でタイを解除するか、代わりに使用することをお勧めします。*s.begin()*s.rbegin()std::multiset

ほとんどの実装では、このようなセットの実装に何らかの形の赤黒木を使用する可能性があります。データ構造は常に並べ替えられたままになるため、漸近的なパフォーマンスは、通常のシングルエンドヒープベースの優先度キューよりも悪くなる可能性がありますが、多くのアプリケーションでは、違いは重要ではないため、実装の労力は重要ではありません。カスタムデータ構造は避ける必要があります。

于 2012-09-17T06:15:05.180 に答える
1

優先キューを使用する！

C ++ STL

#include<queue>

通常、優先キューはBinary-Heapによって実装されます。ただし、最大値と最小値を同時に維持することはできません。@ _ @

たぶん、AVL、Splay、Red-BlackTreeなどのバランスの取れた検索ツリーの方が適しているはずです。

于 2012-09-17T05:36:21.820 に答える
1

通常、プライオリティ キューは、ある種のヒープ構造を使用して実装されます。最大要素と最小要素の両方への一定時間のアクセスを可能にする最小-最大ヒープと呼ばれるバリエーションがあります。このような最小最大ヒープの C++ 実装を求める質問が既にあります。その答えはあなたにも役立つはずです。

Paul Dixonによるこのコメントは最初に min-max ヒープに言及しましたが、 Chris Mansleyによるこのコメントは Stack Overflow に関する実装の質問を指摘しました。

于 2012-09-18T14:55:38.050 に答える
0

データ構造は、優先キューと呼ばれるよく知られた構造です。キュー内の各要素には優先順位が関連付けられており、キューは上位から下位にソートされた順序で保持されます。

キュー内の各要素は優先順位を持っている必要があり、コードは注文契約を維持する必要があります。

一部のSTLには優先度付きキューの実装が含まれていますが、これを見ると、キュー全体が優先度付きで保持されているかどうかがわかりません。

于 2012-09-17T03:21:32.137 に答える