Priority Queue - Colas de prioridad

Las colas de prioridad son estructuras de datos que permiten almacenar elementos con una prioridad asociada. Los elementos se extraen de la cola en orden de prioridad, no en el orden en que fueron añadidos. Esto significa que los elementos con mayor prioridad se procesan antes que los de menor prioridad.

Como usar la documentación

Para leer la guía de uso de la documentación, por favor diríjase a la sección Guía de documentación.

Elementos

pq_entry.py

new_pq_entry(priority, value)

Crea una nueva entrada (de tipo pq_entry) de una cola de prioridad.

La entrada es creada con los siguientes atributos:

priority: Prioridad de la entrada. Inicializada con el valor de la prioridad dada priority.
value: Valor de la entrada. Inicializada con el valor del valor dado value.

Parameters:

priority (any) – Prioridad de la entrada.
value (any) – Valor de la entrada.

Returns:

Entrada de una cola de prioridad.

Return type:

pq_entry

set_priority(my_entry, priority)

Establece un valor nuevo a la priority de una entrada recibida.

Parameters:

my_entry (pq_entry) – Entrada a modificar.
priority (any) – Prioridad nueva de la entrada.

Returns:

Entrada con la prioridad modificada.

Return type:

pq_entry

set_value(my_entry, value)

Establece un valor nuevo al value de una entrada recibida.

Parameters:

my_entry (pq_entry) – Entrada a modificar.
value (any) – Valor nuevo de la entrada.

Returns:

Entrada con el valor modificado.

Return type:

pq_entry

get_priority(my_entry)

Obtiene la prioridad priority de una entrada recibida.

Parameters:: my_entry (pq_entry) – Entrada a modificar.
Returns:: Prioridad de la entrada.
Return type:: any

get_value(my_entry)

Obtiene el valor value de una entrada recibida.

Parameters:: my_entry (pq_entry) – Entrada a modificar.
Returns:: Valor de la entrada.
Return type:: any

Implementaciones

priority_queue.py

new_heap(is_min_pq=True)

Crea un cola de prioridad indexada orientada a menor o mayor dependiendo del valor de is_min_pq

Se crea una cola de prioridad con los siguientes atributos:

elements: Lista de elementos. Se inicializa como una lista vacia de tipo array_list.
size: Tamaño de la cola de prioridad. Se inicializa en 0.
cmp_function: La funcion de comparacion. Si es una cola de prioridad orientada a menor is_min_pq = True, se inicializa con la funcion default_compare_lower_value. Si es una cola de prioridad orientada a mayor is_min_pq = False, se inicializa con la funcion default_compare_higher_value.

Al crear la cola de prioridad, se agrega un elemento None en la posición 0 de la lista de elementos. Esto es útil para poder utilizar la propiedad de los heaps, donde el padre de un nodo en la posición i se encuentra en la posición i//2, y los hijos se encuentran en las posiciones 2*i y 2*i + 1.

Parameters:: is_min_pq (bool) – Indica si la cola de prioridad es orientada a menor o mayor. Por defecto es True.
Returns:: Una nueva cola de prioridad indexada
Return type:: priority_queue

Example:

# App/logic.py
from DataStructures.Priority_queue import priority_queue as pq

# Crea una nueva cola de prioridad
queue = pq.new_heap(True)
print(queue)
# Salida esperada:
# {
#     'elements': {
#         'elements': [None],
#         'size': 1
#     },
#     'size': 0,
#     'cmp_function': <function default_compare_lower_value>
# }

Representación gráfica

        block-beta
    columns 3

    block:elements
        tag["heap:"]
        x["-"]

    end
    space space
    block:pos
        tags["position:"]
        a["0"]

    end

    style elements fill:#fcfcfc,stroke:#fcfcfc
    style pos fill:#fcfcfc,stroke:#fcfcfc
    style tag fill:#fcfcfc,stroke:#fcfcfc
    style tags fill:#fcfcfc,stroke:#fcfcfc
    style a fill:#fcfcfc,stroke:#fcfcfc

default_compare_higher_value(father_node, child_node)

Función de comparación por defecto para el heap orientado a mayor.

Compara la prioridad priority de los nodos father_node y child_node. Si el nodo padre tiene mayor o igual prioridad que el nodo hijo, retorna True. En caso contrario, retorna False.

Parameters:

father_node (pq_entry) – El nodo padre
child_node (pq_entry) – El nodo hijo

Returns:

True si el nodo padre tiene mayor prioridad que el nodo hijo. False en caso contrario.

Return type:

bool

Code:

from DataStructures.Priority_queue import priority_queue as pq
from DataStructures.Priority_queue import pq_entry as pqe

def default_compare_higher_value(father_node, child_node):
    if pqe.get_priority(father_node) >= pqe.get_priority(child_node):
        return True
    return False

default_compare_lower_value(father_node, child_node)

Función de comparación por defecto para el heap orientado a menor.

Compara la prioridad priority de los nodos father_node y child_node. Si el nodo padre tiene menor o igual prioridad que el nodo hijo, retorna True. En caso contrario, retorna False.

Parameters:

father_node (pq_entry) – El nodo padre
child_node (pq_entry) – El nodo hijo

Returns:

True si el nodo padre tiene menor prioridad que el nodo hijo. False en caso contrario.

Return type:

bool

Code:

from DataStructures.Priority_queue import priority_queue as pq
from DataStructures.Priority_queue import pq_entry as pqe

def default_compare_lower_value(father_node, child_node):
    if pqe.get_priority(father_node) <= pqe.get_priority(child_node):
    return True
return False

priority(my_heap, parent, child)

Indica si el parent tiene mayor prioridad que child.

Nota

Esta función es utilizada por las funciones swim() y sink() para dejar el elemento en la posición correcta.

Important

La prioridad se define por la función de comparación del heap. Si es un heap orientado a menor, la prioridad es menor si el parent es menor que el child. Si es un heap orientado a mayor, la prioridad es mayor si el parent es mayor que el child.

Parameters:

my_heap (priority_queue) – El heap a revisar
parent (any) – El elemento padre
child (any) – El elemento hijo a comparar

Returns:

True si el parent tiene mayor prioridad que el child. False en caso contrario.

Return type:

bool

Code:

return my_heap["cmp_function"](parent, child)

insert(my_heap, priority, value)

Agrega una nueva entrada prioridad-valor al heap. Inserta la prioridad priority con valor value en el heap al final de la lista de elementos y luego se hace swim para dejar el elemento en la posición correcta.

Importante

Esta función usa la función swim() para dejar el elemento en la posición correcta.

Parameters:

my_heap (priority_queue) – El heap sobre el cual se realiza la operación
priority (int) – La prioridad a insertar
value (any) – El valor de la nueva entrada

Returns:

El heap con la nueva entrada insertada

Return type:

priority_queue

Example:

# App/logic.py
from DataStructures.Priority_queue import priority_queue as pq

# Crea una nueva cola de prioridad
queue = pq.new_heap(True)
queue = pq.insert(queue, 25, {'name': 'John', 'age': 25})

print(queue)
# Salida esperada:
# {
#   'elements': {
#     'elements': [
#       None,
#       {
#         'priority': 25,
#         'value': {
#           'name': 'John',
#           'age': 25
#         }
#       }
#     ],
#     'size': 2
#   },
#   'size': 1,
#   'cmp_function': <functiondefault_compare_lower_value>
# }

Representación gráfica

        block-beta
    columns 3

    block:elements
        tag["heap (priorities):"]
        z["-"]
        y["25"]


    end
    space space
    block:pos
        tags["position:"]
        a["0"]
        b["1"]

    end

    style elements fill:#fcfcfc,stroke:#fcfcfc
    style pos fill:#fcfcfc,stroke:#fcfcfc
    style tag fill:#fcfcfc,stroke:#fcfcfc
    style tags fill:#fcfcfc,stroke:#fcfcfc
    style a fill:#fcfcfc,stroke:#fcfcfc
    style b fill:#fcfcfc,stroke:#fcfcfc

        graph TD;
    classDef rootnode fill:#fcfcfc,stroke:#fcfcfc;
    classDef circle fill:#3498db,stroke:#fff,stroke-width:3px,rx:50px,ry:50px,color:#fff;
    classDef empty fill:#ccc,stroke:#fff,stroke-width:3px,rx:50px,ry:50px,color:#fff;

    root:::rootnode --> 25:::circle;

Test Scenarios:

Agregar nuevo elemento: Se agrega un nuevo elemento a la cola de prioridad vacia.

# App/logic.py
from DataStructures.Priority_queue import priority_queue as pq

# Crea una nueva cola de prioridad
queue = pq.new_heap(True)
queue = pq.insert(queue, 25, {'name': 'John', 'age': 25})

print(queue)
# Salida esperada:
# {
#   'elements': {
#     'elements': [
#       None,
#       {
#         'priority': 25,
#         'value': {
#           'name': 'John',
#           'age': 25
#         }
#       }
#     ],
#     'size': 2
#   },
#   'size': 1,
#   'cmp_function': <functiondefault_compare_lower_value>
# }

Representación gráfica

        block-beta
    columns 3

    block:elements
        tag["heap (priorities):"]
        z["-"]
        y["25"]


    end
    space space
    block:pos
        tags["position:"]
        a["0"]
        b["1"]

    end

    style elements fill:#fcfcfc,stroke:#fcfcfc
    style pos fill:#fcfcfc,stroke:#fcfcfc
    style tag fill:#fcfcfc,stroke:#fcfcfc
    style tags fill:#fcfcfc,stroke:#fcfcfc
    style a fill:#fcfcfc,stroke:#fcfcfc
    style b fill:#fcfcfc,stroke:#fcfcfc

        graph TD;
    classDef rootnode fill:#fcfcfc,stroke:#fcfcfc;
    classDef circle fill:#3498db,stroke:#fff,stroke-width:3px,rx:50px,ry:50px,color:#fff;
    classDef empty fill:#ccc,stroke:#fff,stroke-width:3px,rx:50px,ry:50px,color:#fff;

    root:::rootnode --> 25:::circle;

Agregar elemento y organiza la prioridad: Se agrega un nuevo elemento a la cola de prioridad y se organiza la prioridad.

# App/logic.py
from DataStructures.Priority_queue import priority_queue as pq

# Crea una nueva cola de prioridad
queue = pq.new_heap(True)
queue = pq.insert(queue, 25, {'name': 'John', 'age': 25})
queue = pq.insert(queue, 30, {'name': 'Jane', 'age': 30})

print(queue)
# Salida esperada:
# {
#   'elements': {
#     'elements': [
#       None,
#       {
#         'priority': 25,
#         'value': {
#           'name': 'John',
#           'age': 25
#         }
#       },
#       {
#         'priority': 30,
#         'value': {
#           'name': 'Jane',
#           'age': 30
#         }
#       }
#     ],
#     'size': 3
#   },
#   'size': 2,
#   'cmp_function': <functiondefault_compare_lower_value>
# }

Representación gráfica

        block-beta
    columns 3

    block:elements
        tag["heap (priorities):"]
        z["-"]
        y["25"]
        x["30"]


    end
    space space
    block:pos
        tags["position:"]
        a["0"]
        b["1"]
        c["2"]

    end

    style elements fill:#fcfcfc,stroke:#fcfcfc
    style pos fill:#fcfcfc,stroke:#fcfcfc
    style tag fill:#fcfcfc,stroke:#fcfcfc
    style tags fill:#fcfcfc,stroke:#fcfcfc
    style a fill:#fcfcfc,stroke:#fcfcfc
    style b fill:#fcfcfc,stroke:#fcfcfc
    style c fill:#fcfcfc,stroke:#fcfcfc

        graph TD;

    classDef rootnode fill:#fcfcfc,stroke:#fcfcfc;
    classDef circle fill:#3498db,stroke:#fff,stroke-width:3px,rx:50px,ry:50px,color:#fff;
    classDef empty fill:#ccc,stroke:#fff,stroke-width:3px,rx:50px,ry:50px,color:#fff;

    root:::rootnode --> 25:::circle;
    25:::circle -->|left| 30:::circle;

swim(my_heap, pos)

Deja en la posición correcta un elemento ubicado en la última posición del heap

Se realiza un recorrido hacia arriba en el heap, comparando el elemento con su padre. Si el elemento tiene mayor prioridad que su padre, se intercambian los elementos y se continúa el recorrido hacia arriba.

Nota

Esta función es utilizada por la función insert() para dejar el elemento en la posición correcta.

Parameters:

my_heap (priority_queue) – El heap sobre el cual se realiza la operación
pos (int) – La posición del elemento a revisar

Example:

# App/logic.py
from DataStructures.Priority_queue import priority_queue as pq

# Crea una nueva cola de prioridad
queue = pq.new_heap(True)
queue = pq.insert(queue, 32, {'name': 'John', 'age': 32})
queue = pq.insert(queue, 47, {'name': 'Alice', 'age': 47})
queue = pq.insert(queue, 18, {'name': 'Bob', 'age': 18})
queue = pq.insert(queue, 22, {'name': 'Charlie', 'age': 22})
print(queue)
# Salida esperada:
# {
#   'elements': {
#     'elements': [
#       None,
#       {
#         'priority': 18,
#         'value': {
#           'name': 'Bob',
#           'age': 18
#         }
#       },
#       {
#         'priority': 22,
#         'value': {
#           'name': 'Charlie',
#           'age': 22
#         }
#       },
#       {
#         'priority': 32,
#         'value': {
#           'name': 'John',
#           'age': 32
#         }
#       },
#       {
#         'priority': 47,
#         'value': {
#           'name': 'Alice',
#           'age': 47
#         }
#       }
#     ],
#     'size': 5
#   },
#   'size': 4,
#   'cmp_function': <functiondefault_compare_lower_value>
# }

queue = pq.insert(queue, 11, {'name': 'Diana', 'age':11})
print(queue)
# Salida esperada:
# {
#   'elements': {
#     'elements': [
#       None,
#       {
#         'priority': 11,
#         'value': {
#           'name': 'Diana',
#           'age': 11
#         }
#       },
#       {
#         'priority': 18,
#         'value': {
#           'name': 'Bob',
#           'age': 18
#         }
#       },
#       {
#         'priority': 32,
#         'value': {
#           'name': 'John',
#           'age': 32
#         }
#       },
#       {
#         'priority': 47,
#         'value': {
#           'name': 'Alice',
#           'age': 47
#         }
#       },
#       {
#         'priority': 22,
#         'value': {
#           'name': 'Charlie',
#           'age': 22
#         }
#       }
#     ],
#     'size': 6
#   },
#   'size': 5,
#   'cmp_function': <functiondefault_compare_lower_value>
# }

Representación gráfica

        block-beta
    columns 2

    block:elements
        tag["heap (priorities):"]
        z["-"]
        y["11"]
        x["18"]
        w["32"]
        v["47"]
        u["22"]


    end
    space space space
    block:pos
        tags["position:"]
        a["0"]
        b["1"]
        c["2"]
        d["3"]
        e["4"]
        f["5"]

    end

    style elements fill:#fcfcfc,stroke:#fcfcfc
    style pos fill:#fcfcfc,stroke:#fcfcfc
    style tag fill:#fcfcfc,stroke:#fcfcfc
    style tags fill:#fcfcfc,stroke:#fcfcfc
    style a fill:#fcfcfc,stroke:#fcfcfc
    style b fill:#fcfcfc,stroke:#fcfcfc
    style c fill:#fcfcfc,stroke:#fcfcfc
    style d fill:#fcfcfc,stroke:#fcfcfc
    style e fill:#fcfcfc,stroke:#fcfcfc
    style f fill:#fcfcfc,stroke:#fcfcfc

        graph TD;

    classDef rootnode fill:#fcfcfc,stroke:#fcfcfc;
    classDef circle fill:#3498db,stroke:#fff,stroke-width:3px,rx:50px,ry:50px,color:#fff;
    classDef empty fill:#ccc,stroke:#fff,stroke-width:3px,rx:50px,ry:50px,color:#fff;

    root:::rootnode --> 11:::circle;
    11:::circle -->|left| 18:::circle;
    11:::circle -->|right| 32:::circle;
    18:::circle -->|left| 47:::circle;
    18:::circle -->|right| 22:::circle;

size(my_heap)

Obtiene el número de elementos en el heap.

Parameters:: my_heap (priority_queue) – El heap del cual se quiere saber la cantidad de elementos
Returns:: El número de elementos
Return type:: int

Example:

# App/logic.py
from DataStructures.Priority_queue import priority_queue as pq

# Crea una nueva cola de prioridad
queue = pq.new_heap(True)

print(pq.size(priority_queue))
# Salida esperada: 0

Test Scenarios:

Heap vacío: Verifica el tamaño de una cola de prioridad vacía.

# App/logic.py
from DataStructures.Priority_queue import priority_queue as pq

# Crea una nueva cola de prioridad
queue = pq.new_heap(True)

print(pq.size(priority_queue))
# Salida esperada: 0

Heap con elementos: Verifica el tamaño de una cola de prioridad después de agregar elementos.

# App/logic.py
from DataStructures.Priority_queue import priority_queue as pq

# Crea una nueva cola de prioridad
queue = pq.new_heap(True)
pq.insert(priority_queue, 1, "A")
pq.insert(priority_queue, 2, "B")
pq.insert(priority_queue, 3, "C")

print(pq.size(priority_queue))
# Salida esperada: 3

Heap después de eliminar elementos: Verifica el tamaño de una cola de prioridad después de eliminar algunos elementos.

# App/logic.py
from DataStructures.Priority_queue import priority_queue as pq

# Crea una nueva cola de prioridad
queue = pq.new_heap(True)
pq.insert(priority_queue, 1, "A")
pq.insert(priority_queue, 2, "B")
pq.insert(priority_queue, 3, "C")

print(pq.size(priority_queue))
# Salida esperada: 3

# Elimina un elemento prioritario
pq.remove(priority_queue)
print(pq.size(priority_queue))
# Salida esperada: 2

Heap después de eliminar todos los elementos: Verifica el tamaño de una cola de prioridad después de eliminar todos los elementos.

# App/logic.py
from DataStructures.Priority_queue import priority_queue as pq

# Crea una nueva cola de prioridad
queue = pq.new_heap(True)
pq.insert(priority_queue, 1, "A")
pq.insert(priority_queue, 2, "B")
pq.insert(priority_queue, 3, "C")

print(pq.size(priority_queue))
# Salida esperada: 3

# Elimina todos los elementos
pq.remove(priority_queue)
pq.remove(priority_queue)
pq.remove(priority_queue)

print(pq.size(priority_queue))
# Salida esperada: 0

is_empty(my_heap)

Verifica si la cola de prioridad está vacía.

Retorna True si el heap está vacío, False en caso contrario. Si el heap tiene un tamaño de 0, se considera vacío.

Parameters:: my_heap (priority_queue) – El heap del cual se quiere saber si está vacío
Returns:: True si el heap está vacío, False en caso contrario.
Return type:: bool

Example:

# App/logic.py
from DataStructures.Priority_queue import priority_queue as pq

# Crea una nueva cola de prioridad
queue = pq.new_heap(True)

print(pq.is_empty(priority_queue))
# Salida esperada: True

Test Scenarios:

Heap vacío: Verifica si una cola de prioridad vacía está vacía.

# App/logic.py
from DataStructures.Priority_queue import priority_queue as pq

# Crea una nueva cola de prioridad
queue = pq.new_heap(True)

print(pq.is_empty(priority_queue))
# Salida esperada: True

Heap con elementos: Verifica si una cola de prioridad con elementos está vacía.

# App/logic.py
from DataStructures.Priority_queue import priority_queue as pq

# Crea una nueva cola de prioridad
queue = pq.new_heap(True)
pq.insert(priority_queue, 1, "A")
pq.insert(priority_queue, 2, "B")
pq.insert(priority_queue, 3, "C")

print(pq.is_empty(priority_queue))
# Salida esperada: False

Heap después de eliminar elementos: Verifica si una cola de prioridad está vacía después de eliminar todos sus elementos.

# App/logic.py
from DataStructures.Priority_queue import priority_queue as pq

# Crea una nueva cola de prioridad
queue = pq.new_heap(True)

# Valida si la cola de prioridad está vacía
print(pq.is_empty(priority_queue))
# Salida esperada: True

pq.insert(priority_queue, 1, "A")
pq.insert(priority_queue, 2, "B")
pq.insert(priority_queue, 3, "C")

print(pq.is_empty(priority_queue))
# Salida esperada: False

# Elimina todos los elementos
pq.remove(priority_queue)
pq.remove(priority_queue)
pq.remove(priority_queue)

# Valida si la cola de prioridad está vacía
print(pq.is_empty(priority_queue))
# Salida esperada: True

get_first_priority(my_heap)

Obtiene el elemento de mayor prioridad del heap sin eliminarlo.

Retorna el primer elemento del heap, es decir el elemento con mayor prioridad sin eliminarlo.

Importante

Si el heap es orientado a menor, el primer elemento es el de menor valor. Si el heap es orientado a mayor, el primer elemento es el de mayor valor.

Parameters:: my_heap (priority_queue) – El heap del cual se quiere obtener el primer elemento
Returns:: El value asociada elemento de mayor prioridad. Si el heap está vacío, retorna None.
Return type:: any

Example:

# App/logic.py
from DataStructures.Priority_queue import priority_queue as pq

# Crea una nueva cola de prioridad
queue = pq.new_heap(True)
queue = pq.insert(queue, 25, {'name': 'John', 'age': 25})
print(pq.get_first_priority(queue))
# Salida esperada:
# {
#   'name': 'John',
#   'age': 25
# }
print(queue)
# Salida esperada:
# {
#   'elements': {
#     'elements': [
#       None,
#       {
#         'priority': 25,
#         'value': {
#           'name': 'John',
#           'age': 25
#         }
#       }
#     ],
#     'size': 2
#   },
#   'size': 1,
#   'cmp_function': <functiondefault_compare_lower_value>
# }

Test Scenarios:

Obtener primer elemento de una cola vacía: Se intenta obtener el primer elemento de una cola de prioridad vacía.

# App/logic.py
from DataStructures.Priority_queue import priority_queue as pq

# Crea una nueva cola de prioridad
queue = pq.new_heap(True)
print(pq.get_first_priority(queue))
# Salida esperada: None

Obtener primer elemento de una cola con elementos: Se obtiene el primer elemento de la cola de prioridad.

# App/logic.py
from DataStructures.Priority_queue import priority_queue as pq

# Crea una nueva cola de prioridad
queue = pq.new_heap(True)
queue = pq.insert(queue, 25, {'name': 'John', 'age': 25})
print(pq.get_first_priority(queue))
# Salida esperada:
# {
#   'name': 'John',
#   'age': 25
# }
print(queue)
# Salida esperada:
# {
#   'elements': {
#     'elements': [
#       None,
#       {
#         'priority': 25,
#         'value': {
#           'name': 'John',
#           'age': 25
#         }
#       }
#     ],
#     'size': 2
#   },
#   'size': 1,
#   'cmp_function': <functiondefault_compare_lower_value>
# }

Obtener primer elemento de una cola despues de modificaciones: Se obtiene el primer elemento de la cola de prioridad con varios elementos y después de realizar modificaciones.

# App/logic.py
from DataStructures.Priority_queue import priority_queue as pq

# Crea una nueva cola de prioridad
queue = pq.new_heap(True)
queue = pq.insert(queue, 25, {'name': 'John', 'age': 25})
queue = pq.insert(queue, 47, {'name': 'Alice', 'age': 47})
queue = pq.insert(queue, 18, {'name': 'Bob', 'age': 18})
print(pq.get_first_priority(queue))
# Salida esperada:
# {
#   'name': 'Bob',
#   'age': 18
# }
print(queue)
# {
#   'elements': {
#     'elements': [
#       None,
#       {
#         'priority': 18,
#         'value': {
#           'name': 'Bob',
#           'age': 18
#         }
#       },
#       {
#         'priority': 47,
#         'value': {
#           'name': 'Alice',
#           'age': 47
#         }
#       },
#       {
#         'priority': 25,
#         'value': {
#           'name': 'John',
#           'age': 25
#         }
#       }
#     ],
#     'size': 4
#   },
#   'size': 3,
#   'cmp_function': <functiondefault_compare_lower_value>
# }

remove(my_heap)

Retorna el elemento del heap de mayor prioridad y lo elimina. Se reemplaza el primer elemento del heap por el último elemento y se hace sink para dejar el elemento en la posición correcta.

Importante

Esta función usa la función sink() para dejar el elemento en la posición correcta.

Parameters:: my_heap (priority_queue) – El heap a revisar
Returns:: value del elemento de mayor prioridad. Si el heap está vacío, retorna None.
Return type:: any

Example:

# App/logic.py
from DataStructures.Priority_queue import priority_queue as pq

# Crea una nueva cola de prioridad
queue = pq.new_heap(True)
queue = pq.insert(queue, 25, {'name': 'John', 'age': 25})
queue = pq.insert(queue, 47, {'name': 'Alice', 'age': 47})
queue = pq.insert(queue, 18, {'name': 'Bob', 'age': 18})
queue = pq.insert(queue, 22, {'name': 'Charlie', 'age': 22})
print(queue)
# Salida esperada:
# {
#   'elements': {
#     'elements': [
#       None,
#       {
#         'priority': 18,
#         'value': {
#           'name': 'Bob',
#           'age': 18
#         }
#       },
#       {
#         'priority': 22,
#         'value': {
#           'name': 'Charlie',
#           'age': 22
#         }
#       },
#       {
#         'priority': 25,
#         'value': {
#           'name': 'John',
#           'age': 25
#         }
#       },
#       {
#         'priority': 47,
#         'value': {
#           'name': 'Alice',
#           'age': 47
#         }
#       }
#     ],
#     'size': 5
#   },
#   'size': 4,
#   'cmp_function': <functiondefault_compare_lower_value>
# }

eliminado = pq.remove(queue)
print(eliminado)
# Salida esperada:
# {
#   'name': 'Bob',
#   'age': 18
# }

print(queue)
# Salida esperada:
# {
#   'elements': {
#     'elements': [
#       None,
#       {
#         'priority': 22,
#         'value': {
#           'name': 'Charlie',
#           'age': 22
#         }
#       },
#       {
#         'priority': 47,
#         'value': {
#           'name': 'Alice',
#           'age': 47
#         }
#       },
#       {
#         'priority': 25,
#         'value': {
#           'name': 'John',
#           'age': 25
#         }
#       }
#     ],
#     'size': 4
#   },
#   'size': 3,
#   'cmp_function': <functiondefault_compare_lower_value>
# }

sink(my_heap, pos)

Deja en la posición correcta un elemento ubicado en la raíz del heap

Se realiza un recorrido hacia abajo en el heap, comparando el elemento con sus hijos. Si el elemento tiene menor prioridad que alguno de sus hijos, se intercambian los elementos y se continúa el recorrido hacia abajo.

Nota

Esta función es utilizada por la función remove() para dejar el elemento en la posición correcta.

Parameters:

my_heap (priority_queue) – El heap sobre el cual se realiza la operación
pos (int) – La posición del elemento a revisar

Example:

# App/logic.py
from DataStructures.Priority_queue import priority_queue as pq

# Crea una nueva cola de prioridad
queue = pq.new_heap(True)
queue = pq.insert(queue, 32, {'name': 'John', 'age': 32})
queue = pq.insert(queue, 47, {'name': 'Alice', 'age': 47})
queue = pq.insert(queue, 18, {'name': 'Bob', 'age': 18})
queue = pq.insert(queue, 22, {'name': 'Charlie', 'age': 22})
queue = pq.insert(queue, 11, {'name': 'Diana', 'age':11})
print(queue)
# Salida esperada:
# {
#   'elements': {
#     'elements': [
#       None,
#       {
#         'priority': 11,
#         'value': {
#           'name': 'Diana',
#           'age': 11
#         }
#       },
#       {
#         'priority': 18,
#         'value': {
#           'name': 'Bob',
#           'age': 18
#         }
#       },
#       {
#         'priority': 32,
#         'value': {
#           'name': 'John',
#           'age': 32
#         }
#       },
#       {
#         'priority': 47,
#         'value': {
#           'name': 'Alice',
#           'age': 47
#         }
#       },
#       {
#         'priority': 22,
#         'value': {
#           'name': 'Charlie',
#           'age': 22
#         }
#       }
#     ],
#     'size': 6
#   },
#   'size': 5,
#   'cmp_function': <functiondefault_compare_lower_value>
# }

# Se elimina el primer elemento de la cola de prioridad
# y se llama a la función sink para organizar la cola
pq.remove(queue)
print(queue)
# Salida esperada:
# {
#   'elements': {
#     'elements': [
#       None,
#       {
#         'priority': 18,
#         'value': {
#           'name': 'Bob',
#           'age': 18
#         }
#       },
#       {
#         'priority': 22,
#         'value': {
#           'name': 'Charlie',
#           'age': 22
#         }
#       },
#       {
#         'priority': 32,
#         'value': {
#           'name': 'John',
#           'age': 32
#         }
#       },
#       {
#         'priority': 47,
#         'value': {
#           'name': 'Alice',
#           'age': 47
#         }
#       }
#     ],
#     'size': 5
#   },
#   'size': 4,
#   'cmp_function': <functiondefault_compare_lower_value>
# }

is_present_value(my_heap, value)

Busca si ya existe una entrada en el heap cuyo valor sea el value. Si existe se retorna la posición de la entrada que contiene el value. Si No existe se retorna el valor -1.

Parameters:

my_heap (priority_queue) – El heap a revisar
value (any) – La parte valor de la entrada del heap que se esta buscando

Returns:

Posición de la entrada si value está presente, -1 en caso contrario.

Return type:

int

contains(my_heap, value)

Busca si ya existe una entrada en el heap cuyo valor sea el value. Si existe se retorna True. En caso contrario, False.

Parameters:

my_heap (priority_queue) – El heap a revisar
value (any) – La parte valor de la entrada del heap que se esta buscando

Returns:

True/False.

Return type:

bool

improve_priority(my_heap, priority, value)

Mejorar la prioridad de la pq_entry que tenga el value dado. Funciona para MinPQ y MaxPQ.

Parameters:

my_heap (priority_queue) – El heap a revisar
priority (int) – La nueva prioridad de la pq_entry del heap. Esta prioridad debe ser mejor que la actual.
value (any) – El value de referencia de la pq_entry del heap que se quiere actualizar

Returns:

El heap con la nueva pq_entry actualizada

Return type:

priority_queue