heapq - max heap python

¿Cómo puedo implementar la funcionalidad de disminución de clave en el heapq de Python?

Question

Sé que es posible realizar una funcionalidad de tecla de disminución en O (log n) pero no sé cómo.

Answer 1

Decrease-key es una operación imprescindible para muchos algoritmos (el algoritmo de Dijkstra, A *, OPTICS), me pregunto por qué la cola de prioridad incorporada de Python no lo admite.

Desafortunadamente, no pude descargar el paquete de math4tots.

Pero, pude encontrar this implementación por Daniel Stutzbach. Funcionó perfectamente para mí con Python 3.5.

hd = heapdict()
hd[obj1] = priority
hd[obj1] = lower_priority
# ...
obj = hd.pop()

Answer 2

Imagina que estás utilizando un montón como una cola de prioridad, donde tienes un montón de tareas representadas por cadenas y cada tarea tiene una clave. Para concretar, mira: task_list = [[7,"do laundry"], [3, "clean room"], [6, "call parents"]] donde cada tarea en task_list es una lista con una prioridad y una descripción. Si ejecuta heapq.heapify(task_list) , obtendrá su matriz para mantener el montón invariante. Sin embargo, si desea cambiar la prioridad de "lavar la ropa" a 1, no tiene forma de saber dónde está "lavar la ropa" en el montón sin un escaneo lineal a través del montón (por lo tanto, no puede hacer disminuir clave en tiempo logarítmico) . Tenga en cuenta que decrease_key(heap, i, new_key) requiere que conozca el índice del valor para cambiar en el montón.

Incluso si mantiene una referencia a cada lista secundaria y realmente cambia la clave, aún no puede hacerlo en el tiempo de registro. Ya que una lista es solo una referencia a un grupo de objetos mutables, puede intentar hacer algo como recordar el orden original de la tarea: (en este caso, "hacer la colada" fue la tarea 0 en su task_list tareas original):

task_list = [[7, "do laundry"], [3, "clean room"], [6, "call parents"]]
task_list_heap = task_list[:] # make a non-deep copy
heapq.heapify(task_list_heap)
# at this point:
# task_list = [[7, ''do laundry''], [3, ''clean room''], [6, ''call parents'']]
# task_list_heap = [3, ''clean room''], [7, ''do laundry''], [6, ''call parents'']]
# Change key of first item of task_list (which was "do laundry") from 7 to 1.
task_list[0][0] = 1
# Now:
# task_list = [[1, ''do laundry''], [3, ''clean room''], [6, ''call parents'']]
# task_list_heap = [3, ''clean room''], [1, ''do laundry''], [6, ''call parents'']]
# task_list_heap violates heap invariant at the moment

Sin embargo, ahora necesita llamar a heapq._siftdown(task_list_heap, 1) para mantener el montón invariante en el tiempo de registro ( heapq.heapify es tiempo lineal), pero desafortunadamente no sabemos el índice de "lavar la ropa" en task_list_heap (el heap_index en este caso es 1).

Por lo tanto, necesitamos implementar nuestro montón para hacer un seguimiento del heap_index de cada objeto; por ejemplo, tenga una list (para el montón) y un dict asigne cada objeto a su índice en el montón / lista (que se actualiza a medida que las posiciones del montón se intercambian agregando un factor constante a cada intercambio). Puede leer a través de heapq.py e implementarse, ya que el procedimiento es sencillo; sin embargo, otros han implementado este tipo de HeapDict ya.

Answer 3

La documentación de heapq tiene una entrada sobre exactamente cómo hacer esto.

Sin embargo, he escrito un paquete de heap que hace exactamente esto (es una envoltura alrededor de heapq ). Así que si tienes pip o easy_install puedes hacer algo como

pip install heap

Luego en tu código escribe

from heap.heap import heap
h = heap()
h[''hello''] = 4 # Insert item with priority 4.
h[''hello''] = 2 # Update priority/decrease-key has same syntax as insert.

Aunque es bastante nuevo, podría estar lleno de errores.

Answer 4

Para implementar "disminuir clave" de manera efectiva, necesitarás acceder a la funcionalidad "disminuir este elemento Y cambiar este elemento con un elemento secundario hasta que se restablezca la condición de montón". En heapq.py , eso se llama _siftdown (y de manera similar _siftup para el Incremento). Entonces, la buena noticia es que las funciones están ahí ... la mala noticia es que sus nombres comienzan con un guión bajo, lo que indica que se consideran "detalles de implementación interna" y que no se debe acceder directamente por el código de la aplicación (la próxima versión de la la biblioteca estándar puede cambiar las cosas y romper el código usando tales "elementos internos").

heapify de usted decidir si desea ignorar la advertencia inicial: _ , use O (N) heapify lugar de O (log N), o vuelva a implementar algunas o todas las funciones de heapq para hacer que las primitivas de tamizado "expuestas como partes públicas de la interfaz ". Dado que la estructura de datos de heapq está documentada y es pública (solo una lista), creo que la mejor opción es probablemente una reimplementación parcial: copie las funciones de cribado de heapq.py en el código de su aplicación, esencialmente.