Eliminación en el montón binario

Question

Estoy tratando de aprender el montón binario y tengo una duda con respecto a hacer la operación de eliminación en el montón binario. He leído que podemos eliminar un elemento del montón binario y tenemos que volver a encontrarlo.

Pero en el siguiente enlace, que dice no disponible:

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 

Estoy algo confundido al respecto.

Gracias de antemano por todas las aclaraciones.

Answer 1

Los montones binarios y otras estructuras de cola de prioridad generalmente no admiten una operación general de "eliminar elemento"; necesita una estructura de datos adicional que realice un seguimiento del índice de cada elemento en el montón, p. una tabla hash. Si usted tiene que, se puede implementar una operación de eliminación general

• hallazgo de elementos, O (1) tiempo de espera con una tabla hash
• decrease key a menos del mínimo, O (lg n) time
• delete-min y actualice la tabla hash, O (lg n) tiempo combinado combinado.

Answer 2

Una eliminación normal es posible, al igual que un DeleteMin/Max. El "problema" es que debe verificar tanto los cambios ascendentes como los descendentes (es decir, cuando el "último" nodo ocupa el lugar vacante, puede estar sobre o subestimado. Como todavía no puede ser ambos, para obvio razones, es fácil verificar la corrección.

El único problema que queda es el Find. La respuesta anterior indica que puede encontrar Element en O (lg n), pero no sé cómo. En mis implementaciones, Generalmente construyo un montón de punteros a elementos en lugar de elementos (copia más barata durante los cambios ascendentes/descendentes). Agrego una variable de "posición" al tipo de Elemento, que realiza un seguimiento del índice del puntero del Elemento en el Heap. manera, dado un elemento E, puedo encontrar su posición en el montón en tiempo constante.

Obviamente, esto no está cortado para cada implem Entation.

Answer 3

No estoy seguro de por qué la operación de eliminación del montón binario se menciona como no disponible en el enlace de su pregunta. La eliminación en el montón binario es bastante posible y su composición de otras 2 operaciones de montón binario. https://en.wikipedia.org/wiki/Binary_heap

Estoy considerando que conoce todas las demás operaciones de binario Montón

Eliminación de una clave del montón binario requiere 2 líneas de código/operación. Supongamos que desea eliminar el elemento en el índice x. Disminuye su valor al entero más bajo posible. Eso es Integer.MIN_VALUE. Como es el valor más bajo de todos los enteros, irá a la posición raíz cuando se ejecute decreaseItem(int index, int newVal). Luego extraiga la raíz que invoca el método 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(); 
} 

Código completo: BinaryHeap_Demo.java