heapq — Algoritmo de ordenación de montículo

Propósito:heapq implementa un algoritmo de ordenación de montículo adecuado para ser usado con listas de Python.

Un montículo es una estructura de datos similar a un árbol en la que los nodos hijos tienen una orden de la relación con los padres. Los montículos binarios pueden ser representados mediante una lista o matriz organizada para que los hijos del elemento N estén en las posiciones 2 * N + 1 y 2 * N + 2 (para índices basados en cero). Este diseño permite reorganizar los montículos en su lugar, por lo que no es necesario reasignar tanta memoria al agregar o eliminando elementos.

Un montículo max asegura que el padre es mayor o igual a ambos de sus hijos. Un montículo min requiere que el padre sea menor que o igual a sus hijos. El módulo heapq de Python implementa un montículo min.

Datos de ejemplo

Los ejemplos en esta sección usan los datos en heapq_heapdata.py.

heapq_heapdata.py
# This data was generated with the random module.

data = [19, 9, 4, 10, 11]

La salida del montículo se imprime usando heapq_showtree.py.

heapq_showtree.py
import math
from io import StringIO


def show_tree(tree, total_width=36, fill=' '):
    """Pretty-print a tree."""
    output = StringIO()
    last_row = -1
    for i, n in enumerate(tree):
        if i:
            row = int(math.floor(math.log(i + 1, 2)))
        else:
            row = 0
        if row != last_row:
            output.write('\n')
        columns = 2 ** row
        col_width = int(math.floor(total_width / columns))
        output.write(str(n).center(col_width, fill))
        last_row = row
    print(output.getvalue())
    print('-' * total_width)
    print()

Creando un montículo

Hay dos formas básicas de crear un montículo: heappush() y heapify().

heapq_heappush.py
import heapq
from heapq_showtree import show_tree
from heapq_heapdata import data

heap = []
print('random :', data)
print()

for n in data:
    print('add {:>3}:'.format(n))
    heapq.heappush(heap, n)
    show_tree(heap)

Cuando se usa heappush(), el orden de clasificación de los elementos se mantiene a medida que se agregan nuevos elementos desde una fuente de datos.

$ python3 heapq_heappush.py

random : [19, 9, 4, 10, 11]

add  19:

                 19
------------------------------------

add   9:

                 9
        19
------------------------------------

add   4:

                 4
        19                9
------------------------------------

add  10:

                 4
        10                9
    19
------------------------------------

add  11:

                 4
        10                9
    19       11
------------------------------------

Si los datos ya están en la memoria, es más eficiente usar heapify() para reordenar los elementos de la lista en su lugar.

heapq_heapify.py
import heapq
from heapq_showtree import show_tree
from heapq_heapdata import data

print('random    :', data)
heapq.heapify(data)
print('heapified :')
show_tree(data)

El resultado de crear una lista en orden montículo un elemento a la vez es el mismo que crear una lista desordenada y luego ejecutar a heapify().

$ python3 heapq_heapify.py

random    : [19, 9, 4, 10, 11]
heapified :

                 4
        9                 19
    10       11
------------------------------------

Accediendo a los contenidos de un montículo

Una vez que el montón esté organizado correctamente, usa heappop() para eliminar el elemento con el valor más bajo.

heapq_heappop.py
import heapq
from heapq_showtree import show_tree
from heapq_heapdata import data

print('random    :', data)
heapq.heapify(data)
print('heapified :')
show_tree(data)
print()

for i in range(2):
    smallest = heapq.heappop(data)
    print('pop    {:>3}:'.format(smallest))
    show_tree(data)

En este ejemplo, adaptado de la documentación de la biblioteca estándar, heapify() y heappop() se usan para ordenar una lista de números.

$ python3 heapq_heappop.py

random    : [19, 9, 4, 10, 11]
heapified :

                 4
        9                 19
    10       11
------------------------------------


pop      4:

                 9
        10                19
    11
------------------------------------

pop      9:

                 10
        11                19
------------------------------------

Para eliminar elementos existentes y reemplazarlos con nuevos valores en una sola operación, usa heapreplace().

heapq_heapreplace.py
import heapq
from heapq_showtree import show_tree
from heapq_heapdata import data

heapq.heapify(data)
print('start:')
show_tree(data)

for n in [0, 13]:
    smallest = heapq.heapreplace(data, n)
    print('replace {:>2} with {:>2}:'.format(smallest, n))
    show_tree(data)

Sustituir los elementos en su lugar hace posible mantener un montículo de tamaño fijo, como una cola de trabajos ordenados por prioridad.

$ python3 heapq_heapreplace.py

start:

                 4
        9                 19
    10       11
------------------------------------

replace  4 with  0:

                 0
        9                 19
    10       11
------------------------------------

replace  0 with 13:

                 9
        10                19
    13       11
------------------------------------

Datos extremos de un montículo

heapq también incluye dos funciones para examinar un iterable y encontrar un rango de los valores más grandes o más pequeños que contiene.

heapq_extremes.py
import heapq
from heapq_heapdata import data

print('all       :', data)
print('3 largest :', heapq.nlargest(3, data))
print('from sort :', list(reversed(sorted(data)[-3:])))
print('3 smallest:', heapq.nsmallest(3, data))
print('from sort :', sorted(data)[:3])

Usar nlargest() y nsmallest() es eficiente solo para valores relativamente pequeños de n > 1, pero aún pueden ser útiles en algunos casos.

$ python3 heapq_extremes.py

all       : [19, 9, 4, 10, 11]
3 largest : [19, 11, 10]
from sort : [19, 11, 10]
3 smallest: [4, 9, 10]
from sort : [4, 9, 10]

Combinando eficiente secuencias ordenadas

La combinación de varias secuencias ordenadas en una nueva secuencia es fácil para pequeños conjuntos de datos.

list(sorted(itertools.chain(*data)))

Para conjuntos de datos más grandes, esta técnica puede usar una cantidad considerable de memoria. En lugar de ordenar toda la secuencia combinada, merge() usa un montículo para generar una nueva secuencia, un elemento a la vez, determinando el siguiente artículo usando una cantidad fija de memoria.

heapq_merge.py
import heapq
import random


random.seed(2016)

data = []
for i in range(4):
    new_data = list(random.sample(range(1, 101), 5))
    new_data.sort()
    data.append(new_data)

for i, d in enumerate(data):
    print('{}: {}'.format(i, d))

print('\nMerged:')
for i in heapq.merge(*data):
    print(i, end=' ')
print()

Debido a que la implementación de merge() usa un montículo, consume memoria basada en el número de secuencias que se fusionan, en lugar del número de elementos en esas secuencias.

$ python3 heapq_merge.py

0: [33, 58, 71, 88, 95]
1: [10, 11, 17, 38, 91]
2: [13, 18, 39, 61, 63]
3: [20, 27, 31, 42, 45]

Merged:
10 11 13 17 18 20 27 31 33 38 39 42 45 58 61 63 71 88 91 95

Ver también