Montículos (heaps) y colas de prioridad: inserción, extracción y heapsort

Una cola normal atiende por orden de llegada. Una cola de prioridad atiende siempre al elemento más importante: el paciente más grave en urgencias, el proceso con más prioridad en un sistema operativo o el nodo más cercano en el algoritmo de Dijkstra. La forma más eficiente de implementarla es el montículo binario (heap): un árbol que se guarda en un simple array y permite insertar y sacar el máximo en

O(\log n)

Lo que vas a aprender

Qué es un montículo y la propiedad de montículo.
Cómo se guarda un árbol binario completo en un array.
La inserción (flotar) y la extracción (hundir).
Cómo construir un montículo en tiempo lineal.
El algoritmo de ordenación heapsort.
Las colas de prioridad y dónde se usan.

Fundamentos teóricos

Definición

Un montículo binario es un árbol binario:

Completo: todos los niveles llenos salvo quizá el último, que se llena de izquierda a derecha.
Con la propiedad de montículo: en un montículo de máximos, cada nodo es mayor o igual que sus hijos (en uno de mínimos, menor o igual).

Por tanto, la raíz es el máximo (o el mínimo). No está ordenado como un árbol de búsqueda: entre hermanos no hay orden.

Representación en un array

Al ser completo, se guarda por niveles en un array sin punteros. Con índices desde 0:

Relación	Índice
Hijo izquierdo de $i$	$2i + 1$
Hijo derecho de $i$	$2i + 2$
Padre de $i$	$\lfloor (i - 1)/2 \rfloor$

Su altura es

\lfloor\log_2 n\rfloor

Insertar: flotar

Se pone el elemento al final del array y se va intercambiando con su padre mientras sea mayor que él. Coste

O(\log n)

Extraer el máximo: hundir

Se saca la raíz, se pone en su lugar el último elemento y se va intercambiando con el mayor de sus hijos mientras sea menor. Coste

O(\log n)

def flotar(a, i):
    while i > 0 and a[(i - 1) // 2] < a[i]:
        p = (i - 1) // 2
        a[i], a[p] = a[p], a[i]
        i = p

def hundir(a, i, n):
    while True:
        mayor, izq, der = i, 2 * i + 1, 2 * i + 2
        if izq < n and a[izq] > a[mayor]: mayor = izq
        if der < n and a[der] > a[mayor]: mayor = der
        if mayor == i:
            return
        a[i], a[mayor] = a[mayor], a[i]
        i = mayor

def insertar(a, x):
    a.append(x)
    flotar(a, len(a) - 1)

def extraer_max(a):
    maximo = a[0]
    a[0] = a[-1]
    a.pop()
    if a:
        hundir(a, 0, len(a))
    return maximo

Construir un montículo: heapify

Para convertir un array cualquiera en un montículo, se hunde cada nodo desde el último padre hasta la raíz:

def construir(a):
    for i in range(len(a) // 2 - 1, -1, -1):
        hundir(a, i, len(a))

Parece

O(n\log n)

, pero es

O(n)

: la mayoría de los nodos están abajo y se hunden muy poco.

Heapsort

Construye un montículo de máximos: $O(n)$ .
Intercambia la raíz (el máximo) con el último elemento, reduce el tamaño en 1 y hunde la nueva raíz. Repite: $O(n\log n)$ .

def heapsort(a):
    construir(a)
    for fin in range(len(a) - 1, 0, -1):
        a[0], a[fin] = a[fin], a[0]
        hundir(a, 0, fin)

Ordena en el mismo array (sin memoria extra) y en

O(n\log n)

siempre, también en el peor caso. A cambio, no es estable y en la práctica suele ser algo más lento que quicksort. Puedes compararlo con otros en el simulador de algoritmos de ordenación.

Colas de prioridad

Operación	Array desordenado	Array ordenado	Montículo binario
Insertar	$O(1)$	$O(n)$	$O(\log n)$
Ver el máximo	$O(n)$	$O(1)$	$O(1)$
Extraer el máximo	$O(n)$	$O(1)$	$O(\log n)$

En Python, heapq implementa un montículo de mínimos sobre una lista; en Java, PriorityQueue; en C++, std::priority_queue (de máximos). Usos: Dijkstra y Prim, planificación de procesos en sistemas operativos, simulación de eventos, el algoritmo de Huffman de compresión, y obtener los

k

mayores de un conjunto enorme sin ordenarlo entero.

Ejemplos resueltos

Ejemplo 1 · Insertar en un montículo de máximos

Montículo [50, 30, 40, 10, 20]. Se inserta 45: queda en el índice 5, cuyo padre es el índice 2 (40).45 > 40: se intercambian → [50, 30, 45, 10, 20, 40]. Padre del índice 2: el 0 (50). 45 < 50: se para.

Ejemplo 2 · Extraer el máximo

De [50, 30, 45, 10, 20, 40] se saca el 50 y el 40 pasa a la raíz: [40, 30, 45, 10, 20].Hijos de la raíz: 30 y 45. El mayor, 45, es mayor que 40: se intercambian → [45, 30, 40, 10, 20]. El 40 ya no tiene hijos: fin.

Ejemplo 3 · Construir en tiempo lineal

Array [3, 9, 2, 1, 4, 5]. Último padre: índice 2.

Índice 2 (2): hijo 5 → [3, 9, 5, 1, 4, 2].
Índice 1 (9): hijos 1 y 4, es mayor: no cambia.
Índice 0 (3): hijos 9 y 5 → intercambia con 9: [9, 3, 5, 1, 4, 2]; el 3 tiene hijos 1 y 4 → con 4: [9, 4, 5, 1, 3, 2].

Resultado: [9, 4, 5, 1, 3, 2].

Ejemplo 4 · Los 3 mayores de un millón de datos

Con un montículo de mínimos de tamaño 3: se recorre el millón de datos y, si un dato es mayor que la raíz (el menor de los 3 guardados), se sustituye. Coste

O(n\log k)

en lugar de

O(n\log n)

de ordenar todo.

import heapq
mayores = heapq.nlargest(3, datos)

Errores frecuentes

Pensar que un montículo está ordenado. Solo está garantizado que la raíz es el máximo (o mínimo).
Hundir intercambiando con cualquier hijo. Hay que elegir el mayor (o el menor, en uno de mínimos).
Equivocar los índices según se empiece en 0 o en 1: con base 1, los hijos son $2i$ y $2i + 1$ .
Usar heapq como montículo de máximos. Es de mínimos; para máximos, se guardan los valores cambiados de signo.
Construir insertando uno a uno ( $O(n\log n)$ ) cuando ya se tiene el array: heapify es $O(n)$ .

Preguntas frecuentes

¿Qué tiene que ver con el 'heap' de la memoria?

Nada, salvo el nombre. El heap de memoria (donde se reserva con malloc o new) es una zona de memoria dinámica; el montículo es una estructura de datos. Lo primero se explica en memoria y punteros en C.

¿Hay montículos más rápidos?

Los montículos de Fibonacci bajan el coste de “disminuir clave” a

O(1)

amortizado, lo que mejora Dijkstra en teoría a

O(E + V\log V)

. En la práctica, por sus constantes, el montículo binario suele ganar.

Temas relacionados

Algoritmos de ordenación

Heapsort frente a los demás.

Dijkstra y caminos mínimos

El uso más famoso de una cola de prioridad.

Árboles AVL

Árboles de búsqueda equilibrados.

Matemáticas

Física

Química

Electrónica

Programación

Inglés

Infantil

Montículos (heaps) y colas de prioridad: inserción, extracción y heapsort

Lo que vas a aprender

Fundamentos teóricos

Definición

Representación en un array

Insertar: flotar

Extraer el máximo: hundir

Construir un montículo: heapify

Heapsort

Colas de prioridad

Ejemplos resueltos

Errores frecuentes

Preguntas frecuentes

Temas relacionados

Algoritmos de ordenación

Dijkstra y caminos mínimos

Árboles AVL

​Lo que vas a aprender

​Fundamentos teóricos

​Definición

​Representación en un array

​Insertar: flotar

​Extraer el máximo: hundir

​Construir un montículo: heapify

​Heapsort

​Colas de prioridad

​Ejemplos resueltos

​Errores frecuentes

​Preguntas frecuentes

​Temas relacionados

Algoritmos de ordenación

Dijkstra y caminos mínimos

Árboles AVL

Lo que vas a aprender

Fundamentos teóricos

Definición

Representación en un array

Insertar: flotar

Extraer el máximo: hundir

Construir un montículo: heapify

Heapsort

Colas de prioridad

Ejemplos resueltos

Errores frecuentes

Preguntas frecuentes

Temas relacionados