Python: eliminar elemento del montón

Question

Python tiene el módulo heapq que implementa la estructura de datos del montón y admite algunas operaciones básicas (push, pop).

Como eliminar i-th elemento del montón en O (log n)? ¿Es posible con heapq o tengo que usar otro módulo?

Nota, hay un ejemplo en la parte inferior de la documentación: http://docs.python.org/library/heapq.html que sugieren un posible enfoque; esto no es lo que quiero. Quiero que el elemento se elimine, no que simplemente marque como eliminado.

Answer 1

Se puede quitar el elemento i-ésimo de un montón bastante facilidad:

h[i] = h[-1] 
h.pop() 
heapq.heapify(h) 

basta con sustituir el elemento que desea eliminar con el último elemento y eliminar el último elemento a continuación, volver a heapify el montón. Esto es O (n), si lo deseas, puedes hacer lo mismo en O (log (n)), pero necesitarás llamar a un par de las funciones internas de heapify, o mejor, como larsmans señaló simplemente copiar la fuente de _siftup/_siftdown de heapq.py en su propio código:

h[i] = h[-1] 
h.pop() 
if i < len(h): 
    heapq._siftup(h, i) 
    heapq._siftdown(h, 0, i) 

Tenga en cuenta que en cada caso no se puede simplemente hacer h[i] = h.pop() ya que sería un error si i hace referencia al último elemento. Si su caso especial elimina el último elemento, entonces podría combinar la sobrescritura y el pop.

Tenga en cuenta que dependiendo del tamaño típico de su montón podría encontrar que sólo llamar heapify aunque teóricamente menos eficiente podría ser más rápido que la reutilización de _siftup/_siftdown: un poco de introspección revelará que heapify es, probablemente, implementado en C pero la implementación C de las funciones internas no está expuesta. Si el rendimiento le resulta importante, considere realizar algunas pruebas de tiempo en datos típicos para ver cuál es el mejor. A menos que tenga montones realmente grandes, la O grande no es el factor más importante.

Editar: alguien trató de editar esta respuesta para eliminar la llamada a _siftdown con un comentario que: no es necesario

_siftdown. Se garantiza que h nueva [i] es la más pequeña de las hijas del viejo h [i], que aún es más grande que el padre del viejo h [i] (padre nuevo h [i]). _siftdown será un no-op. Tengo que editar desde que no tengo suficientes representantes para agregar un comentario todavía.

Lo que han perdido en este comentario es que h[-1] podría no ser un hijo de h[i] en absoluto. El nuevo valor insertado en h[i] podría provenir de una rama completamente diferente del montón, por lo que podría necesitar ser tamizado en cualquier dirección.

también al comentario preguntando por qué no sólo tiene que utilizar sort() para restaurar el montón: llamar _siftup y _siftdown son ambos O (log n) operaciones, llamando heapify es O (n).Llamar al sort() es una operación O (n log n). Es bastante posible que la ordenación de llamada sea lo suficientemente rápida, pero para grandes montones es una sobrecarga innecesaria.

Editado para evitar el problema señalado por @Seth Bruder. Cuando i hace referencia al elemento final, la llamada _siftup() fallará, pero en ese caso, si se saca un elemento del final del almacenamiento dinámico no se rompe la constante de almacenamiento dinámico.

Answer 2

(a) Considere por qué no desea la eliminación diferida. Es la solución correcta en muchos casos.

(b) Un montón es una lista. Puede eliminar un elemento por índice, como cualquier otra lista, pero luego tendrá que volver a heapificarlo, porque ya no satisfará el invariante de montón.