Eliminar un nodo del centro de un montón

Question

Eliminar un nodo del centro del montón se puede hacer en O (lg n) siempre que podamos encontrar el elemento en el montón en tiempo constante. Supongamos que el nodo de un montón contiene id como su campo. Ahora, si proporcionamos el id, ¿cómo podemos eliminar el nodo en O (lg n) time?

Una solución puede ser que podemos tener una dirección de una ubicación en cada nodo, donde mantenemos el índice del nodo en el montón. Esta matriz se ordenaría por ID de nodo. Esto requiere una matriz adicional para mantenerse. ¿Hay algún otro método bueno para lograr lo mismo?

PD: Me encontré con este problema al implementar el algoritmo de ruta más corta de Djikstra.

Answer 1

El índice (id, nodo) se puede mantener por separado en una tabla hash que tiene O (1) complejidad de búsqueda (en promedio). La complejidad general sigue siendo O (log n).

Answer 2

Cada estructura de datos está diseñada con ciertas operaciones en mente. De Wikipedia acerca de las operaciones del montón

 
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. 

Esto significa, montón no es la mejor estructura de datos para la operación que busca. Le aconsejaría que busque una estructura de datos más adecuada (según sus requisitos).