Eliminar un elemento de una cola de prioridad

Question

En Python, el módulo heapq proporciona una cola de prioridad.

Tiene métodos para insertar y abrir elementos.

¿Cómo se elimina un elemento que ha insertado que no es la prioridad más baja de la cola?

(recetas alternativas para hacer esto utilizando otras colecciones alternativas también son bienvenidos)

Answer 1

El módulo heapq utiliza listas de Python estándar como estructura de datos subyacente, por lo que sólo se puede utilizar el estándar list método remove() y heapify() de nuevo después de esto. Sin embargo, tenga en cuenta que esto necesitará tiempo lineal.

# Create example data and heapify 
a = range(10) 
a.reverse() 
heapq.heapify(a) 
print a 

# remove an element and heapify again 
a.remove(5) 
heapq.heapify(a) 
print a 

Se podría mejorar el rendimiento de heapifying de nuevo utilizando la función indocumentado heapify._siftup(), pero todo el proceso todavía será O (n), ya que list.remove() es O (n).

Answer 2

Hay una estructura de datos llamada treap que es una cola de prioridad y un árbol binario combinados. (árbol-montón). Permite la búsqueda de log-n que podría ayudarte.

Hay una Python treap implementation on PyPi ..;)

Answer 3

Este registro (N) La función es eficaz para mí:

def heapq_remove(heap, index): 
    """Remove item from heap""" 

    # Move slot to be removed to top of heap 
    while index > 0: 
     up = (index + 1)/2 - 1 
     heap[index] = heap[up] 
     index = up 

    # Remove top of heap and restore heap property 
    heapq.heappop(heap) 

Answer 4

Si conoce la ubicación del elemento que desea eliminar, se puede hacer lo siguiente :

a[k] = a.pop() 
heapq.heapify(a) 

el primer paso es ahora O (1) el tiempo, y la segunda se puede hacer O (log (N)) mediante el uso de los datos sin papeles. Por supuesto, sigue siendo O (N) para encontrar k si aún no lo tienes.