Minheap e rimozione dell'elemento se i dati cambiano tra le rimozioni

Question

Ho fatto una domanda ieri ma non era molto chiara, quindi questa è una domanda più specifica.

Sto rappresentando il mio minheap come array. Ho una buona conoscenza dei minheap, penso, ma sono sfocato su un determinato concetto all'interno. Si suppone che i Minheap abbiano sempre il nodo più piccolo come root. Per eliminare un valore, la radice viene impostata sull'ultimo elemento nella rappresentazione dell'array (un nodo foglia) e la dimensione dell'array viene decrementata. Il nodo radice viene quindi posizionato correttamente usando siftDown/PercolateDown o qualsiasi altra cosa si voglia chiamare. Questo è super efficiente. Ad esempio:

Qui 29 è stato ripreso l'ultimo elemento e siftDown (1) si posizionarlo:

1. 29 viene confrontato con 15 e 38. Cambio 29 e 15.
2. 29 viene confrontato con 25 e 20. Scambio 29 e 20.
3. 29 viene confrontato con 30, 29 < 30 quindi abbiamo finito.

Questo è tutto a posto, ma cosa succede se tra 2 istanze di rimozione del minimo, alcune delle altre modifiche dei dati? Per esempio:

Ecco, allora:

1. 29 viene confrontato con il 15 e il 38. Cambio 29 e 15.
2. 29 viene confrontato con 30 e 32. 29 < 30 e 29 < 32 quindi abbiamo finito.

1 è il valore più piccolo nella struttura, ma non è stato impostato come minimo, 15 è stato. Questo è un grosso problema per me. Sto cercando di implementare l'algoritmo Dijkstras, sto anche cercando di utilizzare le mie strutture dati senza toccare le classi java integrate.

Così un esempio più rilevante per il mio problema sarebbe:

Per chi ha familiarità con Dijkstra, 99 rappresenta una distanza tentativo di infinito e di altri numeri rappresentano nodi del grafo che dovrebbe essere visitato successiva (la nodo con la distanza più piccola, in questo caso 3).

Una soluzione è ricostruire l'albero ogni volta che rimuovo min, tuttavia ciò significa che la potenza di un minheap è persa e qualsiasi implementazione rallenta fino alla ricerca per indicizzazione.

Mi scuso se non lo sto capendo correttamente ma sono rimasto bloccato per giorni e ho davvero bisogno di aiuto.

Answer 1

È necessario comprendere la pre-condizione dell'algoritmo. L'algoritmo siftDown non funziona con alcun array arbitrario. Funziona solo quando il figlio sinistro e il figlio destro sono heap.

Nel secondo esempio, il figlio sinistro della radice non è un min-heap. Quindi, l'algoritmo non produrrà un min-heap.

Ci deve essere qualcosa che non va nella vostra applicazione se si finisce in una matrice che viola la proprietà mucchio, come il numero di immagine 3.