Löschen eines Knotens aus der Mitte eines Heapspeichers

Question

Das Löschen eines Knotens aus der Mitte des Heapspeichers kann in O (lg n) erfolgen, vorausgesetzt, das Element im Heap kann in konstanter Zeit gefunden werden. Angenommen, der Knoten eines Heap enthält id als Feld. Nun, wenn wir die ID bereitstellen, wie können wir den Knoten in O (Ign) -Zeit löschen?

Eine Lösung kann sein, dass wir eine Adresse eines Ortes in jedem Knoten haben können, wo wir den Index des Knotens im Heap pflegen. Dieses Array würde nach Knoten-IDs geordnet sein. Dies erfordert jedoch, dass ein zusätzliches Array beibehalten wird. Gibt es noch eine andere gute Methode, um dasselbe zu erreichen?

PS: Ich stieß auf dieses Problem bei der Implementierung von Djikstra Shortest Path-Algorithmus.

Answer 1

Der Index (ID, Knoten) kann separat in einer Hashtabelle verwaltet werden, die im Durchschnitt eine (1) Suchkomplexität aufweist. Die Gesamtkomplexität bleibt dann O (log n).

Answer 2

Jede Datenstruktur wurde für bestimmte Operationen entwickelt. Aus Wikipedia über Heap-Operationen

 
The operations commonly performed with a heap are: 
create-heap: create an empty heap 
find-max or find-min: find the maximum item of a max-heap or a minimum item of a min-heap, respectively 
delete-max or delete-min: removing the root node of a max- or min-heap, respectively 
increase-key or decrease-key: updating a key within a max- or min-heap, respectively 
insert: adding a new key to the heap 
merge joining two heaps to form a valid new heap containing all the elements of both. 

Das bedeutet, ist Heap nicht die beste Datenstruktur für den Betrieb die Sie suchen. Ich würde Ihnen empfehlen, nach einer besser geeigneten Datenstruktur zu suchen (abhängig von Ihren Anforderungen).