18

キュー内のアイテムの優先度を変更できるプライオリティ キューを実装する必要があり、アイテムが常に正しい順序で削除されるようにキューが調整されます。これを実装する方法についていくつかのアイデアがありますが、これは非常に一般的なデータ構造であると確信しているので、私よりも賢い人による実装をベースとして使用できることを願っています.

このタイプのプライオリティ キューの名前を誰か教えてもらえますか?検索対象がわかるように、または実装を教えてもらえますか?

4

5 に答える 5

11

このようなプライオリティ キューは通常、他の誰かが提案したようにバイナリ ヒープ データ構造を使用して実装されます。これは通常、配列を使用して表されますが、バイナリ ツリーを使用することもできます。ヒープ内の要素の優先度を増減するのは、実際には難しくありません。次の要素がキューから取り出される前に多くの要素の優先度を変更していることがわかっている場合は、動的な並べ替えを一時的にオフにし、すべての要素をヒープの最後に挿入してから、ヒープ全体を並べ替えることができます (コストがかかります)。 of O(n)) 要素をポップする必要がある直前。ヒープに関する重要な点は、配列をヒープの順序に並べ替えるのに O(n) しかかからず、並べ替えるのに O(n log n) かかることです。

私は、動的な優先順位を持つ大規模なプロジェクトでこのアプローチをうまく使用しました。

これは、Curl プログラミング言語でのパラメーター化されたプライオリティ キューの実装の私の実装です。

于 2010-05-06T15:28:53.430 に答える
5

標準のバイナリ ヒープは 5 つの操作をサポートします (以下の例では、最大ヒープを想定しています)。

* find-max: return the maximum node of the heap
* delete-max: removing the root node of the heap
* increase-key: updating a key within the heap
* insert: adding a new key to the heap
* merge: joining two heaps to form a valid new heap containing all the elements of both.

ご覧のとおり、最大ヒープでは、任意のキーを増やすことができます。最小ヒープでは、任意のキーを減らすことができます。残念ながら、キーを両方の方法で変更することはできませんが、これは可能でしょうか? 両方の方法でキーを変更する必要がある場合は、 aa min-max-heap の使用を検討することをお勧めします。

于 2010-02-18T12:16:16.273 に答える
2

優先度を更新するために、最初に正面からのアプローチを試すことをお勧めします。

  • キューからアイテムを削除する
  • 新しい優先度で再挿入します

C++ では、これは を使用して行うことができますstd::multi_map。重要なことは、オブジェクトが構造内のどこに格納されているかをオブジェクトが記憶し、それ自体を効率的に削除できるようにすることです。再挿入の場合、優先順位について何も知らないと仮定できないため、難しいです。

class Item;

typedef std::multi_map<int, Item*> priority_queue;

class Item
{
public:
  void add(priority_queue& queue);
  void remove();

  int getPriority() const;
  void setPriority(int priority);

  std::string& accessData();
  const std::string& getData() const;

private:
  int mPriority;
  std::string mData;

  priority_queue* mQueue;
  priority_queue::iterator mIterator;
};

void Item::add(priority_queue& queue)
{
  mQueue = &queue;
  mIterator = queue.insert(std::make_pair(mPriority,this));
}

void Item::remove()
{
  mQueue.erase(mIterator);
  mQueue = 0;
  mIterator = priority_queue::iterator();
}

void Item::setPriority(int priority)
{
  mPriority = priority;
  if (mQueue)
  {
    priority_queue& queue = *mQueue;
    this->remove();
    this->add(queue);
  }
}
于 2010-02-19T15:23:48.950 に答える
0

Google には、 Javaでの実装など、さまざまな回答があります。

ただし、これは宿題の問題のように聞こえるので、そうである場合は、最初に自分でアイデアを検討してから、どこかで行き詰まって正しい方向へのポインターが必要な場合は、他の人の実装を参照することをお勧めします。 . そうすれば、他のプログラマーが使用する正確なコーディング方法に「偏る」可能性が低くなり、コードの各部分が含まれる理由とそれがどのように機能するかを理解する可能性が高くなります. 場合によっては、「コピー アンド ペースト」に相当する言い換えを行いたくなることがあります。

于 2010-02-18T11:43:47.400 に答える
0

まったく同じものを探しています！

そして、ここに私の考えのいくつかがあります：

  1. アイテムの優先度は常に変化するため、アイテムを取得する前にキューをソートしても意味がありません。
  2. したがって、プライオリティ キューの使用を忘れる必要があります。また、アイテムの取得中にコンテナを「部分的に」ソートします。

また、次の STL ソート アルゴリズムから選択します。パーティション b. stable_partition c. nth_element d. partial_sort e. partial_sort_copy ｆ．ソート g. 安定ソート

partition、stable_partition、および nth_element は線形時間ソート アルゴリズムであり、これを最初に選択する必要があります。

しかし、公式のJavaライブラリで提供されているアルゴリズムはないようです。その結果、java.util.Collections.max/min を使用して目的を達成することをお勧めします。

于 2010-05-06T10:52:32.683 に答える