Prioritätswarteschlange mit Operationen zum Verringern des Schlüssels und zum Erhöhen des Schlüssels

11

Ein Fibonnaci-Heap unterstützt die folgenden Vorgänge:

  • insert(key, data) : Fügt der Datenstruktur ein neues Element hinzu
  • find-min() : Gibt einen Zeiger auf das Element mit dem minimalen Schlüssel zurück
  • delete-min() : Entfernt das Element mit dem minimalen Schlüssel
  • delete(node) : löscht das Element, auf das von zeigt node
  • decrease-key(node) : verringert den Schlüssel des Elements, auf das von zeigt node

Alle Nichtlöschvorgänge sind (amortisierte) Zeit, und die Löschvorgänge sind O ( log n ) amortisierte Zeit.Ö(1)Ö(Logn)

Gibt es Implementierungen einer Prioritätswarteschlange, die auch increase-key(node)in (amortisierter) Zeit unterstützt werden?Ö(1)

Joe
quelle
@Raphael Wenn Sie den Schlüssel des minimalen Elements so erhöhen , dass es jetzt der größte Schlüssel ist, ist es (zumindest für mich) nicht sofort offensichtlich, dass Sie keine überkonstante Neuausrichtung durchführen müssen.
Joe

Antworten:

10

O(1) find-minincrease-keyinsertO(n)

vector<T>
fast_sort(const vector<T> & in) {
  vector<T> ans;
  pq<T> out;
  for (auto x : in) {
    out.insert(x);
  }
  for(auto x : in) {
    ans.push_back(*out.find_min());
    out.increase_key(out.find_min(), infinity);
  }
  return ans;
}
jbapple
quelle
1
Ich hatte angenommen, dass (de|in)crease-keynur plus oder minus eins.
Raphael
Und gibt es einen DS, der es ermöglicht, die Tasten in konstanter Zeit zu erhöhen, aber logarithmisch (oder mehr) zu verringern? (Für einen Min-Haufen)
Gonzalo Solera
2
@GonzaloSolera: Der Unmöglichkeitsbeweis in dieser Antwort kümmert sich nicht um den Abnahmeschlüssel. O (1) find-min, Erhöhungsschlüssel und Einfügen sind bereits zusammen ein Problem (und die Abhängigkeit des Beweises vom Einfügen ist nicht wirklich notwendig; O (n) Heapify ist ausreichend, oder wir können wahrscheinlich denselben Heap über mehrere wiederverwenden sortiert, um zu beweisen, dass es die Vergleichssortiergrenzen verletzt, unabhängig von den Kosten für Heapify oder Insert).
user2357112 unterstützt Monica
Okay, tut mir leid, ich habe das nicht gelesen. Vielen Dank für Ihren Kommentar!
Gonzalo Solera