3

次のステートメントをどこかで読んでください。

追加のハッシュ テーブルを使用して、最小ヒープでの削除を高速化できます。

priority_queue質問>とを組み合わせunordered_mapて上記のアイデアを実装するにはどうすればよいですか?

#include <queue>
#include <unordered_map>
#include <iostream>
#include <list>
using namespace std;

struct Age
{
  Age(int age) : m_age(age) {}
  int m_age;  
};

// Hash function for Age
class HashAge {
  public:
   const size_t operator()(const Age &a) const {
     return hash<int>()(a.m_age);
   }
};

struct AgeGreater
{
  bool operator()(const Age& lhs, const Age& rhs) const {
    return lhs.m_age < rhs.m_age;
  }
};

int main()
{
  priority_queue<Age, list<Age>, AgeGreater> min_heap;          // doesn't work
  //priority_queue<Age, vector<Age>, AgeGreater> min_heap;

  // Is this the right way to do it?
  unordered_map<Age, list<Age>::iterator, HashAge > hashTable;     
}

質問> 以下の作業ができません。

priority_queue<Age, list<Age>, AgeGreater> min_heap;          // doesn't work

リストをコンテナーとして使用する必要があります b/c リストの反復子は挿入/削除の影響を受けません (反復子の無効化規則)

4

1 に答える 1

4

priority_queue提供されたデータ構造ではこれを行うことはできません。

優先キューでは、要素がどこに保存されているかわからないため、要素を見つけることができないため、一定時間内に要素を削除することは困難です。しかし、ハッシュ テーブルに保存されたプライオリティ キュー内のすべての要素の場所を使用してハッシュ テーブルを維持すると、アイテムをすばやく見つけて削除できますが、最悪の場合は log(N) 時間であり、一定ではありません。時間。（一定の時間を償却した場合、私はすぐに覚えていません。）

これを行うには、通常、独自のデータ構造をロールする必要があります。これは、項目が優先キュー内を移動するたびにハッシュ テーブルを更新する必要があるためです。

ここにこれを行うサンプルコードがあります：

http://code.google.com/p/hog2/source/browse/trunk/algorithms/AStarOpenClosed.h

古いコーディング スタイルに基づいていますが、機能します。

説明する：

/**
 * Moves a node up the heap. Returns true if the node was moved, false otherwise.
 */
template<typename state, typename CmpKey, class dataStructure>
bool AStarOpenClosed<state, CmpKey, dataStructure>::HeapifyUp(unsigned int index)
{
        if (index == 0) return false;
        int parent = (index-1)/2;
        CmpKey compare;

        if (compare(elements[theHeap[parent]], elements[theHeap[index]]))
        {
                // Perform normal heap operations
                unsigned int tmp = theHeap[parent];
                theHeap[parent] = theHeap[index];
                theHeap[index] = tmp;
                // Update the element location in the hash table
                elements[theHeap[parent]].openLocation = parent;
                elements[theHeap[index]].openLocation = index;
                HeapifyUp(parent);
                return true;
        }
        return false;
}

ステートメント内ifでは、ヒープに対して通常の heapify 操作を実行し、ハッシュ テーブル ( openLocation) 内の場所を更新して、優先キュー内の現在の場所を指すようにします。

于 2013-08-21T17:30:59.210 に答える