Heap y Priority Queue usando el módulo heapq en Python

Los montones son estructuras de datos en forma de árbol ampliamente utilizadas en las que los Nodes principales cumplen cualquiera de los criterios que se indican a continuación.

• El valor del Node principal en cada nivel es menor o igual que los valores de sus hijos: min-heap.
• El valor del Node padre en cada nivel superior o igual a los valores de sus hijos: max-heap.

Los montones son árboles binarios completos y se utilizan en la implementación de las colas de prioridad. Los montones mínimos juegan un papel vital en la programación de trabajos, la programación de correos electrónicos o la asignación de recursos a tareas según la prioridad. 

colas de prioridad

Estos son tipos de datos abstractos y son una forma especial de colas. Los elementos de la cola tienen asignadas prioridades. Según las prioridades, el primer elemento de la cola de prioridad será el que tenga la prioridad más alta. Las operaciones básicas asociadas con estas colas de prioridad se enumeran a continuación: 

• is_empty: para comprobar si la cola está vacía.
• insert : Para insertar un elemento junto con su prioridad. El elemento se colocará únicamente en el orden de su prioridad.
• pop : Para hacer estallar el elemento con la prioridad más alta. El primer elemento será el elemento con la prioridad más alta.

Las colas de prioridad se pueden utilizar para todo tipo de procesos de programación. El programador puede decidir si el número más grande se considera como la prioridad más alta o el número más bajo se considerará como la prioridad más alta. Si dos elementos tienen la misma prioridad, aparecen en el orden en que aparecen en la cola. 

módulo heapq en Python

El módulo Heapq es una implementación del algoritmo de cola de montón (algoritmo de cola de prioridad) en el que se conserva la propiedad de min-heap. El módulo toma una lista de elementos y la reorganiza de modo que satisfagan los siguientes criterios de montón mínimo:

• El Node padre en el índice ‘i’ es menor o igual que sus hijos.
• El hijo izquierdo de un Node en el índice ‘i’ está en el índice ‘(2*i) + 1’ .
• El hijo derecho de un Node en el índice ‘i’ está en el índice ‘(2*i) + 2’ .

Colas de prioridad usando el módulo heapq

La cola de prioridad se implementa en Python como una lista de tuplas donde la tupla contiene la prioridad como primer elemento y el valor como el siguiente elemento.

Ejemplo: [ (1, 2), (2, 3), (4, 5), (6,7)]

considere (1,2) : 

• Prioridad 1
• Valor/elemento: 2

Ejemplo:

Considere una implementación de cola de prioridad simple para programar las presentaciones de los estudiantes en función de su número de lista. Aquí el número de lista decide la prioridad del estudiante para presentar. Dado que es un montón mínimo, el rollo número 1 se considera de máxima prioridad.

# import modules
import heapq as hq
  
# list of students
list_stu = [(5,'Rina'),(1,'Anish'),(3,'Moana'),(2,'cathy'),(4,'Lucy')]
  
# Arrange based on the roll number
hq.heapify(list_stu)
  
print("The order of presentation is :")
  
for i in list_stu:
  print(i[0],':',i[1])

The order of presentation is :
1 : Anish
2 : cathy
3 : Moana
5 : Rina
4 : Lucy

Ejemplo 2:

Ahora implementemos un programador simple que asigne los trabajos al procesador. El programador utiliza la cola de prioridad para decidir qué tarea se debe realizar. Aparte de las tareas, habrá interrupciones acercándose al planificador. Entonces, el programador tiene que decidir si ejecutar la interrupción o la tarea existente. Si la interrupción tiene una prioridad más alta, se ejecuta primero; de lo contrario, una vez que se completan todos los trabajos, se atenderá la interrupción. Para implementar esto se utiliza el módulo heapq. El enfoque se da a continuación.

• Las tareas a ejecutar se asignan con prioridades. El elemento que tiene ‘1’ como prioridad se considera la tarea más importante.
• Todas las tareas están en una cola de prioridad y se mantienen con la propiedad min-heap.
• Las tareas se atienden y, mientras están en curso, solo se imprime un mensaje como un registro de ejecución que indica qué tarea está en curso.
• Las interrupciones junto con sus prioridades se acercan al planificador.
• Las interrupciones se envían a la cola de prioridad conservando la propiedad min-heap.
• La tarea/interrupción con la prioridad más alta será atendida primero y siempre es el primer elemento en la cola.
• Una vez que se atiende una interrupción de tareas, se extrae de la cola del montón.

import time
import heapq as hq
  
# jobs to be executed
jobs = [(2, 'task_1'), (5, 'task_2'), (1, 'task_4'),
        (4, 'task_5'), (3, 'task_3'), (1, 'task_8')]
  
# interrupts
interrupts = [(1, 'intr_1'), (2, 'intr_2'), (13, 'intr_3')]
  
i, j = 0, 0
  
# Arranging jobs in heap
hq.heapify(jobs)
  
print(jobs, "\n\n")
  
# scheduling the tasks
while len(jobs) != 0:
  
    # printing execution log
    print("The ", jobs[0][1], " with priority ",
          jobs[0][0], " in progress", end="")
  
    # servicing the tasks
    for _ in range(0, 5):
  
        print(".", end="")
        time.sleep(0.5)
  
    # pop the job that completed
    hq.heappop(jobs)
  
    # adding interrupts
    if j < len(interrupts):
  
        hq.heappush(jobs, interrupts[j])
        print("\n\nNew interrupt arrived!!", interrupts[j])
        print()
        j = j+1
  
    # job queue after arrival of interrupt
    print("\n Job queue currently :", jobs)
    print("\n")
  
  
print("\nAll interrupts and jobs completed!")

Producción