Priority queue mit dynamische-posten-Prioritäten

Muss ich implementieren Sie eine Warteschlange, wo die Priorität eines Elements in die Warteschlange ändern kann, und die Warteschlange stellt sich so, dass Elemente immer entfernt, in der richtigen Reihenfolge. Ich habe einige Ideen, wie ich Sie verwirklichen könnte, aber ich bin sicher, dies ist eine ganz gewöhnliche Daten-Struktur, so bin ich der Hoffnung, dass ich verwenden können, um eine Implementierung von jemand schlauer als ich als Basis.

Kann mir jemand sagen, der name dieser Art von Priorität in der Warteschlange, so weiß ich, was zu suchen oder, besser noch, zeigen Sie mir eine Umsetzung?

Siehe stackoverflow.com/questions/927631/... und stackoverflow.com/questions/450180/...

InformationsquelleAutor sean | 2010-02-18

  1. 2

    Ich würde vorschlagen, zuerst versuchen, die Kopf-in-Ansatz, um die update-Priorität:

    • löschen Sie das Element aus der Warteschlange
    • re-legen Sie es mit der neuen Priorität

    In C++, dies könnte getan werden, mit einem std::multi_map, das wichtigste ist, dass das Objekt muss daran erinnern, wo es gespeichert wird, in der Struktur, um in der Lage sein, um sich selbst zu löschen effizient. Für neu einfügen, es ist schwierig, da Sie nicht davon ausgehen, Sie wissen alles über die Prioritäten.

    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);
  }
}
    Danke Matthieu, ich dachte über die Verwendung dieser Ansatz aber aufgrund der update-Häufigkeit war es nicht effizient genug für meine Bedürfnisse. Ich landete mit einer Implementierung, dass eine Wörterbuch-mapping-Elemente zu Ihrer Indizes in der Warteschlange, dann eine Methode in der Warteschlange, UpdatePosition(Element Element), sieht sich die Einzelteile index und dann sprudelte es an seine neue position. Die Warteschlange hat dann ein Ereignis, dass die Elemente, registrieren gegen, so dass Sie informieren Sie die Warteschlange, wenn Sie Ihre Prioritäten ändern. Das scheint gut zu funktionieren.

    InformationsquelleAutor Matthieu M.

  2. 8

    Priority queues wie diese sind in der Regel umgesetzt in einem binären heap-Datenstruktur als jemand anderes vorgeschlagen, die in der Regel vertreten ist, mit einem array könnte aber auch ein binärer Baum. Es ist eigentlich nicht schwer zu erhöhen oder verringern Sie die Priorität eines Elements im heap. Wenn Sie wissen, Sie werden ändern der Priorität von vielen Elemente, bevor Sie das nächste element tauchte aus der Warteschlange können Sie vorübergehend deaktivieren Sie die dynamische Neuanordnung, legen Sie alle Elemente, die am Ende des heap, und Sortieren Sie dann den gesamten heap (zu Kosten von O(n)) kurz bevor das element muss geknallt werden. Die wichtige Sache über den Haufen, dass es nur Kosten O(n), um ein array in den heap, um aber O(n log n) zu Sortieren.

    Ich habe diesen Ansatz erfolgreich in einem großen Projekt mit dynamischen Prioritäten.

    Hier ist meine Umsetzung eines parametrisierten priority queue-Implementierung in der Programmiersprache Curl.

    InformationsquelleAutor Christopher Barber

  3. 5

    Einem standard-Binär-heap unterstützt-5-Operationen (im Beispiel unten wird davon ausgegangen, ein max-heap):

    * 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.

    Wie Sie sehen können, in einem max-heap, erhöhen Sie eine beliebige Taste. In einem min-heap kann eine Verringerung einer beliebigen Taste. Sie können nicht ändern, die Tasten mit beiden Möglichkeiten, leider aber wird das tun? Wenn Sie brauchen, um Schlüssel in beide Richtungen, dann möchten Sie vielleicht denken über die Verwendung einer ein min-max-heap.

    Ich sehe nicht, wie man einen binären heap könnte effizient Unterstützung zu erhöhen-Taste, wenn Sie zuerst suchen müssen für das element, das Sie möchten, zu erhöhen. Da es keine Sortierung in den Haufen, es dauert lineare Zeit, um das element.
    Sie müssen einen Verweis auf das element, um erhöhen-Taste verringern-Taste effiziente. Umgesetzt wird dies mit Griffen in den Boost.Heap-C++ - Bibliothek boost.org/doc/libs/1_55_0/doc/html/heap/...

    InformationsquelleAutor Martin

  4. 0

    Google hat eine Reihe von Antworten für Sie, einschließlich einer Umsetzung der eine in Java.

    Jedoch, das wie etwas klingt, das wäre ein Hausaufgaben problem, also wenn es so ist, würde ich vorschlagen, versuchen, Arbeit durch die Ideen selbst zuerst, dann möglicherweise Referenzierung jemand anderes die Umsetzung, wenn Sie irgendwo stecken und brauchen einen Zeiger in die richtige Richtung. So, Sie sind weniger wahrscheinlich zu sein "voreingenommen" gegenüber die genaue Codierung-Methode verwendet, durch die weitere Programmierer und eher zu verstehen, warum jedes Stück code enthalten ist und wie es funktioniert. Manchmal kann es ein wenig zu verlockend, zu tun, die Umschreibung entspricht der "kopieren und einfügen".

    Dank Dav, aber dies ist eine standard-Priorität-Warteschlange. Wenn ich ein Element hinzufügen, um die Warteschlange und es wird die Priorität geändert wird (außerhalb der queue), die Reihenfolge der Warteschlange ist möglicherweise falsch. In anderen Worten, eine standard-Priorität-Warteschlange nur möglichen Gegenstände, wenn Sie Hinzugefügt, um die Warteschlange und nicht später. Muss ich implementieren Sie eine Warteschlange, die updates, wie die Priorität der Objekte aktualisiert. P. S. Es ist nicht ein Hausaufgaben problem, ich brauche, um dies zu implementieren, als Teil der Simulations-software. Ich habe einige Ideen, wie ich das umsetzen kann, es aber wollen, um zu sehen, ob es einen besseren Weg, es zu tun.
    Ah. Okay. In diesem Fall würde ich vorschlagen, nach Beispiel-Implementierungen des Dijkstra-Algorithmus, die (wenn Sie denn umgesetzt werden-in Ihrer effizientesten form) erfordert eine verschiebbare priority queue, und damit sollte wohl das haben, was Sie suchen.

    InformationsquelleAutor Amber

  5. 0

    Ich Suche gerade genau das gleiche!

    Und hier ist meine Idee:

    1. Da die Priorität eines Elements ändert sich ständig,
      es ist sinnlos, um die Sortierung der Warteschlange vor dem abrufen eines Elements.
    2. So ist, sollten wir vergessen die Verwendung einer priority-queue. Und "teilweise" Sortieren
      container beim abrufen eines Elements.

    Und wählen Sie aus der folgenden STL-sort-algorithmen:
    ein. partition
    b. stable_partition
    c. nth_element
    d.... partial_sort
    e. partial_sort_copy
    f. Sortieren
    g. stable_sort

    partition, stable_partition und nth_element linear-time-sort-algorithmen, die unsere 1. Wahl.

    ABER, es scheint, dass es gibt keine solche algorithmen in der offiziellen Java-Bibliothek. Als Ergebnis, ich schlage vor, Sie verwenden java.util.Sammlungen.min/max zu tun, was Sie wollen.

    InformationsquelleAutor Henry

Schreibe einen Kommentar