Eliminazione nell'heap binario

Question

Sto solo cercando di imparare l'heap binario e ho un dubbio sull'operazione di eliminazione nell'heap binario. Ho letto che possiamo eliminare un elemento dall'heap binario e abbiamo bisogno di riorganizzarlo.

Ma al seguente link, si dice disponibile:

http://en.wikibooks.org/wiki/Data_Structures/Tradeoffs

   Binary Search AVL Tree Binary Heap (min) Binomial Queue (min) 

Find   O(log n)  O(log n) unavailable   unavailable 
Delete element O(log n  O(log n) unavailable   unavailable 

Sono po 'confuso su di esso.

Grazie in anticipo per tutti i chiarimenti.

Answer 1

Gli heap binari e altre strutture di coda di priorità non supportano generalmente un'operazione di "eliminazione elemento" generale; è necessaria una struttura dati aggiuntiva che tenga traccia dell'indice di ciascun elemento nell'heap, ad es. una tabella hash. Se si dispone di che, è possibile implementare un'operazione di eliminazione generale

• find-elemento, O (1) tempo previsto con una tabella di hash
• decrease key a meno del minimo, O (lg n) time
• delete-min e aggiornare la tabella hash, O (lg n) tempo previsto combinato.

Answer 2

Una cancellazione regolare è possibile, proprio come un DeleteMin/Max. Il "problema" è che devi controllare sia verso l'alto che verso il basso (cioè: quando il nodo "ultimo" occupa il posto libero, può essere sopravvalutato o sottovalutato. Poiché non può ancora essere entrambi, per ovvi motivi, è facile verificare la correttezza.

l'unico problema che rimane è la Trova. la risposta di cui sopra afferma che si può trovare Elemento a O (lg n), ma non saprei come fare. nei miei implementazioni, Generalmente faccio un Heap di puntatori agli elementi piuttosto che a elementi (copia più economica durante le scalate/scalate). Aggiungo una variabile "posizione" al tipo di elemento, che tiene traccia dell'indice del puntatore dell'elemento nell'heap. modo, dato un elemento E, posso trovare la sua posizione nel mucchio in tempo costante

Ovviamente, questo non è tagliato per ogni implem entazione.

Answer 3

Sono confuso perché l'operazione di eliminazione dell'heap binario è menzionata come non disponibile nel collegamento della domanda. La cancellazione nell'heap binario è abbastanza possibile ed è la composizione di 2 altre operazioni di heap binario. https://en.wikipedia.org/wiki/Binary_heap

Sto considerando di sapere tutte le altre operazioni di Binary Heap

Eliminazione di una chiave da heap binario richiede 2 linee di codice/funzionamento. Supponiamo di voler eliminare l'elemento nell'indice x. Diminuisci il valore al più basso numero intero possibile. Quello è Integer.MIN_VALUE. Dal momento che è il valore più basso di tutto il numero intero andrà alla posizione principale quando l'esecuzione di decreaseItem(int index, int newVal) è stata completata. Successivamente estrarre la radice invocando il metodo extractMin().

// Complexity: O(lg n) 
public void deleteItem(int index) { 
    // Assign lowest value possible so that it will reach to root 
    decreaseItem(index, Integer.MIN_VALUE); 
    // Then extract min will remove that item from heap tree. correct ? 
    extractMin(); 
} 

codice completo: BinaryHeap_Demo.java