Esta es la segunda entrega de la serie de estructuras de datos anunciada al final del artículo sobre pilas y colas. La protagonista es la heap, pero antes debemos aclarar un malentendido.
En el artículo relacionado Guía completa de pilas y colas: por qué Swift no tiene un tipo Stack (incluida la trampa de removeFirst) puedes consultar los conceptos de base y casos de aplicación relacionados.
**El heap de una estructura de datos solo comparte nombre con el heap de memoria; no tienen relación.**El área heap de la memoria es espacio de asignación dinámica; el heap de este artículo es «un árbol para extraer el mínimo (o máximo) en O(1)».
La diferencia entre las áreas de asignación de memoria se explica por separado en Pila vs heap. Aquí nos centramos únicamente en las estructuras Heap y Priority Queue.
Si esperabas el heap del artículo «pila vs heap», este es un mundo completamente distinto.
El problema que resuelve un heap es claro.
«Quiero procesar primero lo más urgente, pero ordenar todo de antemano sería desperdiciar recursos».
Ordenar es excesivo
Supongamos que creamos una cola que extrae primero la tarea con mayor prioridad. Ordenar el array cada vez cuesta O(n log n) en cada inserción.
Incluso manteniendo el orden y buscando la posición de inserción, mover elementos cuesta O(n).
Pensándolo bien, no necesitamos que todo esté ordenado. Basta con conocer de inmediato el elemento más urgente.
No pasa nada por averiguar quién ocupa el segundo lugar después de que salga el primero.
Eso es exactamente lo único que garantiza un heap. Por eso tanto insertar como eliminar termina en O(log n).
«Cuanto menos prometes, más rápido eres» es una compensación clásica del diseño de estructuras de datos.
Regla del heap: el padre es menor que sus hijos; eso es todo
Un heap mínimo es un árbol binario completo con una sola regla.
Cada padre es menor o igual que sus hijos.
No importa cuál de los hermanos sea mayor. El subárbol izquierdo tampoco tiene que ser menor que el derecho.
Solo hay que respetar la relación padre-hijo. Gracias a esta flexibilidad, la raíz siempre contiene el mínimo global, pero no se garantiza nada más.
Inserción (sift up): se añade al final del árbol y, si es menor que su padre, se intercambia y sube. Solo recorre la altura del árbol: O(log n).
Extraer el mínimo (sift down): se quita la raíz, se lleva el último elemento a ella y se baja intercambiándolo con el menor de sus dos hijos. También es O(log n).
La magia de crear un árbol con un array
Aquí está la elegancia del heap. Un árbol binario completo se llena de izquierda a derecha, así que puede colocarse en un array en orden sin punteros.(NIST Heap).
Índice: 0 1 2 3 4 5
Valor: [1, 3, 2, 7, 4, 5]Las relaciones familiares salen solo con calcular índices.
- Padre:
(i - 1) / 2 - Hijo izquierdo:
2i + 1, hijo derecho:2i + 2
No hay objetos nodo, punteros a hijos ni asignación de memoria heap. Aprovechamos la localidad de caché tratada en array vs lista enlazada y tomamos solo la estructura lógica del árbol.
Este es el esqueleto en Swift.
struct MinHeap<Element: Comparable> {
private var elements: [Element] = []
var min: Element? { elements.first } // O(1)
mutating func insert(_ value: Element) { // O(log n)
elements.append(value)
siftUp(from: elements.count - 1)
}
mutating func removeMin() -> Element? { // O(log n)
guard !elements.isEmpty else { return nil }
elements.swapAt(0, elements.count - 1)
let min = elements.removeLast()
siftDown(from: 0)
return min
}
}siftUp/siftDown son las iteraciones de intercambio descritas arriba.
Por cierto, convertir un array existente completo en heap mediante build-heap no cuesta O(n log n) por insertar cada elemento. Hacer sift down desde la mitad inferior termina en O(n); es un detalle frecuente en entrevistas.
El lugar del heap en la práctica
**Una cola de prioridad es un heap.**Siguiendo la terminología del artículo sobre pilas y colas, una cola extrae por orden de llegada y una cola de prioridad por urgencia; el heap es su implementación estándar (NIST Priority Queue).
- Planificador del SO: asigna la CPU primero a los procesos de mayor prioridad
- Ruta mínima de Dijkstra: algoritmo que extrae repetidamente «la ruta más corta encontrada hasta ahora»; sin heap, el rendimiento se degrada
- Gestión de temporizadores: estructura interna que solo necesita conocer cuál de muchos temporizadores sonará primero
- Heapsort: insertar y extraer todos los elementos produce una ordenación O(n log n). Su ventaja es ordenar in situ sin memoria adicional
- Problema Top-K: «mantener los K mayores de un flujo»; se resuelve en O(n log K) con un heap mínimo de tamaño K. Es un patrón habitual en pruebas de programación
La biblioteca estándar de Swift no incluye heap. Como Deque en el artículo sobre pilas y colas, el paquete de Apple swift-collections proporciona Heap (swift-collections Heap).
Esta implementación de min-max heap admite min y max en O(log n). Si no se permiten paquetes externos, como en una prueba de programación, conviene dominar el esqueleto MinHeap anterior.
Resumen
- El heap de una estructura de datos solo comparte nombre con el heap de memoria: es «un árbol que extrae el mínimo al instante»
- Solo se cumple padre ≤ hijo: renunciar a ordenar todo permite insertar y eliminar en O(log n)
- Al ser un árbol binario completo, puedecolocarse en un array sin punteros: padre
(i-1)/2, hijos2i+1,2i+2 - El heap es la implementación estándar de una cola de prioridad; Dijkstra, los planificadores y Top-K son usos representativos
- En Swift, swift-collections ofrece
Heap; en pruebas de programación, implementarlo a mano es lo habitual
La próxima entrega tratará las tablas hash: cómo Swift Dictionary consigue O(1) y qué significan realmente los requisitos de Hashable.
Fuentes y verificación
- swift-collections HeapApple · Documentación oficial · Consultado 17 de agosto de 2026Respalda: API Heap de Swift y comportamiento de heaps mínimo y máximo
- NIST Dictionary of Algorithms: Priority QueueNIST · Datos oficiales · Consultado 17 de agosto de 2026Respalda: Definición del tipo abstracto de datos de una cola de prioridad
- NIST Dictionary of Algorithms: HeapNIST · Datos oficiales · Consultado 17 de agosto de 2026Respalda: Estructura y características operativas de un heap basado en arrays