algorithm - programacion - ¿Cómo eliminar en una estructura de datos de montón?
listas lineales estructura de datos (4)
¿Entiendo cómo eliminar el nodo raíz de un montón máximo, pero es el procedimiento para eliminar un nodo del centro para eliminar y reemplazar la raíz repetidamente hasta que se elimine el nodo deseado?
¿Es O (log n) la complejidad óptima para este procedimiento?
¿Afecta esto la gran complejidad O ya que otros nodos se deben eliminar para eliminar un nodo específico?
El problema al eliminar un elemento arbitrario de un montón es que no puede encontrarlo.
En un montón, buscar un elemento arbitrario es O(n) , eliminando así un elemento [si está dado por valor] es O(n) también.
Si es importante que elimine los elementos arbitrarios de la estructura de datos, un montón probablemente no sea la mejor opción; en su lugar, debería considerar los estructuradores de datos completos ordenados como BST balanceada o una lista de omisiones .
Si su elemento está dado por referencia, es posible eliminarlo en O(logn) simplemente ''reemplazándolo'' con la última hoja [recuerde que un montón está implementado como un árbol binario completo, por lo que hay una última hoja, y sabes exactamente dónde está], elimina estos elementos y vuelve a heapificar el sub montón relevante.
En realidad, puedes eliminar un elemento de la mitad de un montón sin problemas.
La idea es tomar el último elemento del montón y, comenzando desde la posición actual (es decir, la posición que contenía el elemento que eliminó), cribarlo si el nuevo elemento es mayor que el elemento principal del elemento anterior. Si no es mayor que el padre, luego cribalo.
Ese es el procedimiento para un montón máximo. Por un montón mínimo, por supuesto, invertirías el mayor y el menor número de casos.
Encontrar un elemento en un montón es una operación O (n), pero si ya sabe dónde está en el montón, eliminarlo es O (log n).
Publiqué una cola de prioridad basada en el montón para DevSource hace unos años. Consulte Implementación de cola de prioridad en C # . Tiene un método RemoveAt que hace exactamente lo que describí.
La fuente completa está en http://www.mischel.com/pubs/priqueue.zip
Actualizar
Varios han preguntado si es posible moverse hacia arriba después de mover el último nodo en el montón para reemplazar el nodo eliminado. Considera este montón:
1
6 2
7 8 3
Si elimina el nodo con el valor 7, el valor 3 lo reemplaza:
1
6 2
3 8
Ahora debe moverlo hacia arriba para crear un montón válido:
1
3 2
6 8
La clave aquí es que si el elemento que está reemplazando está en un subárbol diferente que el último elemento en el montón, es posible que el nodo de reemplazo sea más pequeño que el padre del nodo reemplazado.
Lo que quiere lograr no es una operación de montón típica y me parece que una vez que introduce "eliminar elemento medio" como un método, otro árbol binario (por ejemplo, árbol rojo-negro o AVL) es una mejor opción. Tiene un árbol rojo-negro implementado en algunos idiomas (por ejemplo, mapa y configurado en c ++).
De lo contrario, la forma de eliminar el elemento medio es la propuesta en la respuesta de rejj: asigne un gran valor (para el máximo) o pequeño (para el montón mínimo) al elemento, crítelo hasta que sea raíz y luego elimínelo.
Este enfoque aún mantiene la complejidad O (log (n)) para la eliminación del elemento medio, pero el que usted propone sí lo hace. Tendrá comlexidad O (n * log (n)) y por lo tanto no es muy bueno. Espero que ayude.
Si tiene un montón máximo, puede implementar esto asignando un valor mayor que cualquier otro (por ejemplo, algo como int.MaxValue o inf en el idioma que esté utilizando) posible al elemento que se eliminará, luego volver a heapify y lo hará ser la nueva raíz Luego realice una eliminación regular del nodo raíz.
Esto causará otro re-heapify, pero no veo una manera obvia de evitar hacerlo dos veces. Esto sugiere que tal vez un montón no sea apropiado para su caso de uso, si necesita extraer nodos desde el medio a menudo.
(para un montón mínimo, obviamente puede usar int.MinValue o -inf o lo que sea)