Warum betonen die Leute, dass Heaps zum Implementieren von Prioritätswarteschlangen verwendet werden, weil die Zeitkomplexität des Spähens bei einem maximalen/minimalen Wert O (1) ist.
Kann dies nicht einfach auf einem bst implementiert werden, indem der Zeiger verwendet wird, um auf den Knoten ganz rechts/ganz links zu zeigen.Warum sind Prioritätswarteschlangen als binärer Heap implementiert?
Es kann, aber es als Heap effizienter und einfacher ist, da die Spitze eines Heaps leichter zu verfolgen ist als das linke Element eines Baumes (die Spitze eines Heaps ist nur die erste Element der zugrunde liegenden Sequenz).
Angesichts der Tatsache, dass Sie eine auf BST basierende Prioritätswarteschlange vorschlagen, werde ich versuchen, Ihnen zu erklären, warum ein Heap besser ist als ein BST.
Ein Heap ist ein vollständiger Baum; es ist ein perfekt ausgewogener Baum. Seine Höhe ist log_2(n+1).
Ein BST-Ansatz lohnt sich, wenn dieser ausgewogen ist. Die am besten bekannte Technik zum Aufrechterhalten eines ausgeglichenen BST ist ein AVL-Baum. Diese Baumart hat eine Höhenbegrenzung von 1.44 log_2(n+2) - 0.33.
Für die Konsultation von Minimum haben Sie eine Kosten von O(log(n)) für eine BST gegenüber O(1) für einen Haufen. Für diese Operation ist der Haufen eindeutig besser.
Zum Einfügen und Löschen sind die Kosten asymptotisch äquivalent. Aber die BST ist tendenziell teurer, weil ihre Höhe tendenziell höher ist als ein perfekt ausgewogener Baum. Darüber hinaus verbraucht ein AVL-Baum mehr Zeit als ein Heap. In der AVL (und auch in anderen Balancing-Ansätzen, Rot-Schwarz-Baum, Treaps, Splays, etc.) führen Sie Rotationen durch, während Sie mit dem Heap Swaps durchführen, die günstiger sind als Rotationen.
Löschen auf BST ist eine komplizierte und ständig teure Operation und könnte O(log(n)) Umdrehungen dauern. Mit einem Heap ist O(log(n)) Swaps, die erinnern, sind billiger, dass Rotationen.
Schließlich, im Falle einer Einfügung, könnten Sie O(log(n)) Swaps für den Haufen und höchstens zwei Umdrehungen für die AVL durchführen. Aber mit der Einfügung in eine AVL müssen Sie eine erfolglose Suche durchführen, während der Heap Sie den neuen Schlüssel direkt einfügen können, bevor Sie mit dem Tauschen beginnen. Ich denke, dass nur mit dem Einfügen ein BST manchmal einen Haufen schlagen konnte. Berücksichtigen Sie jedoch, dass Sie höchstwahrscheinlich eine Prioritätswarteschlange für Konsultationen und Löschungen verwenden würden. Also, wenn dies der Fall ist, dann werden Sie sicherlich die Zeit wiederherstellen, die Sie verlieren könnten, wenn Sie die Einfügungen gemacht haben.
Darüber hinaus ist ein Heap viel einfacher zu implementieren als ein BST, wenn Sie ein Array verwenden, das den Level-Traversal des vollständigen Baums speichert. In diesem Fall brauchen Sie keine Zeiger
https://en.wikipedia.org/wiki/Priority_queue#Usual_implementation –
Sie können nicht Zugriff auf den linken/rechten Knoten in einem BST in * O (1) * Zeit. – EJP
@EJP Ich hatte die C++ STL-Map im Hinterkopf und fragt dies ... es implementiert Rot-Schwarz-Baum und hat diese Memberfunktion 'end', die Ihnen den Maximalwert in const Zeit zurückgibt ... sehr ähnlich wie wir zuletzt zugreifen können Knoten einer verknüpften Liste, denke ich. –