Eliminazione di un nodo dal centro di un heap

Question

L'eliminazione di un nodo dal centro dell'heap può essere eseguita in O (lg n), a condizione che sia possibile trovare l'elemento nell'heap in un tempo costante. Supponiamo che il nodo di un heap contenga l'id come suo campo. Ora se forniamo l'id, come possiamo eliminare il nodo in O (lg n) tempo?

Una soluzione può essere che possiamo avere un indirizzo di una posizione in ogni nodo, dove manteniamo l'indice del nodo nell'heap. Questo array sarebbe ordinato per id dei nodi. Ciò richiede però che venga mantenuta una matrice aggiuntiva. C'è qualche altro buon metodo per raggiungere lo stesso.

PS: mi sono imbattuto in questo problema mentre implementavo l'algoritmo Shortest Path di Djikstra.

Answer 1

L'indice (id, nodo) può essere mantenuto separatamente in una tabella hash con una complessità di ricerca O (1) (in media). La complessità complessiva rimane O (log n).

Answer 2

Ogni struttura di dati è progettata tenendo conto di determinate operazioni. Da wikipedia sulle operazioni heap

 
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. 

Ciò significa, mucchio non è la migliore struttura dei dati per l'operazione che si sta cercando. Ti consiglio di cercare una struttura dati più adatta (in base alle tue esigenze) ..