Usuwanie węzła ze środka sterty

Question

Usuwanie węzła ze środka sterty można wykonać w O (lg n), pod warunkiem, że możemy znaleźć element w stercie w stałym czasie. Załóżmy, że węzeł sterty zawiera id jako swoje pole. Teraz, jeśli podamy identyfikator, jak możemy usunąć węzeł w czasie O (lg n)?

Jednym z rozwiązań może być to, że możemy mieć adres lokalizacji w każdym węźle, gdzie utrzymujemy indeks węzła w stercie. Ta tablica byłaby uporządkowana według identyfikatorów węzła. Wymaga to jednak dodatkowej tablicy. Czy jest jakaś inna dobra metoda na osiągnięcie tego samego.

PS: Natknąłem się na ten problem podczas wdrażania algorytmu najkrótszej ścieżki Djikstry.

Answer 1

Indeks (identyfikator, węzeł) może być przechowywany osobno w tablicy, która ma złożoność O (1) (średnio). Ogólna złożoność pozostaje wtedy O (log n).

Answer 2

Każda struktura danych została zaprojektowana z myślą o określonych operacjach. Z Wikipedii o operacjach stertowych

 
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. 

Oznacza to, że sterty nie są najlepszą strukturą danych dla operacji, której szukasz. Poradziłbym ci, abyś szukał lepiej dopasowanej struktury danych (w zależności od twoich wymagań).