Heaps y colas de prioridad
Mapa conceptual
- Estructuras de Datos
- Lineales
- Arrays
- Listas enlazadas
- Pilas y Colas
- No lineales
- Arboles BST
- Heaps
- Grafos
- Hash
- Funcion hash
- Colisiones
- Rehashing
- Algoritmos
- Ordenamiento
- Busqueda binaria
- BFS DFS
- Optimizacion
- Big-O
- Dinamica
- Voracidad
- Lineales
La propiedad de heap
- Es un árbol BINARIO COMPLETO: lleno hasta el penúltimo nivel y alineado a la izquierda.
- Cumple la propiedad de orden: en un min-heap, cada padre es menor o igual que sus hijos.
- La raíz es, por transitividad, el mínimo global; pero un nodo no es menor que el hijo de otro ramo.
Representación en arreglo
Como el árbol es completo, no necesita punteros: se guarda en un arreglo. El hijo izquierdo del nodo i está en 2i+1, el derecho en 2i+2, y el padre en (i−1)/2. Toda la navegación es aritmética de índices, lo que lo hace compacto y amigable con la memoria.
Sift up y sift down
Insertar = colocar al final y subir (sift up) mientras sea menor que su padre. Extraer el mínimo = llevar la raíz al final, y hundir (sift down) el nuevo tope hasta su lugar. Ambos recorren la altura del árbol, que en un completo es log n.
| Operación | Costo | Por qué |
|---|---|---|
| peek (ver el mínimo) | O(1) | Vive en la raíz |
| push (insertar) | O(log n) | Recorre la altura subiendo |
| pop (extraer extremo) | O(log n) | Hunde el reemplazo por la altura |
| construir desde lista (heapify) | O(n) | Los nodos bajos casi no se mueven |
Cola de prioridad
Una cola de prioridad es un contenedor que siempre devuelve el elemento de mayor (o menor) prioridad. El heap es su implementación estrella: push y pop en log n. Aparece en planificadores de procesos, en el algoritmo de Dijkstra, en compresión Huffman y en cualquier «atender primero lo más urgente».
f(x) = 2 ^ x · f(x) = x · f(x) = log(x)+1
¿Por qué un heap ofrece el mínimo en O(1) pero NO ordena todos sus elementos?
Heap vs árbol binario de búsqueda
Un BST ordenado da recorrido completo en O(n log n) y búsqueda O(log n), pero se desbalancea. Un heap no sirve para buscar un valor arbitrario (O(n)), a cambio su acceso al extremo y su equilibrio estructural son garantizados por ser completo. Cada estructura elige qué promesa dar.
Heapsort
Heapsort convierte el arreglo en un heap y luego extrae el extremo una y otra vez, colocando cada elemento al final. Ordena in situ en O(n log n) garantizado, sin el peor caso O(n²) de quicksort, aunque con peores patrones de memoria (menos locality).
Construir un heap a partir de n elementos desordenados puede hacerse en tiempo O(n).
Errores frecuentes
- Confundir heap con árbol ordenado: el heap no permite búsquedas eficientes de un valor dado.
- Olvidar que el pop deja «basura» al final del arreglo: hay que reducir el tamaño lógico.
- Suponer estabilidad: el heap NO conserva el orden de elementos empatados.
Variantes
El max-heap invierte la desigualdad; un heap binomial o de Fibonacci admite operaciones extra como disminuir clave en tiempo amortizado, útil para grafos. Para un estudiante, el binario basta y es la base sobre la que se entienden los demás.
Anatomía del heap
Toca una tarjeta para ver la respuesta.
Cuando Python hace heapq.heappush, no mantiene un arreglo ordenado: mantiene un heap. Pedir el mínimo es gratis; saber cuál es el tercero más pequeño requeriría extraer dos veces. Entender ese intercambio es entender para qué sirve la estructura.
Ordena las fases de un heapsort:
Arrastra cada ficha a su categoría (o tócala y luego toca la categoría). También puedes usar el teclado.
GeeksforGeeksHeap binario, heapify y colas de prioridad con código.
Elige un uso real de una cola de prioridad (un scheduler, GPS con Dijkstra, merge de K listas). Explica por qué un heap encaja mejor que un arreglo ordenado o que una lista desordenada, señalando qué operación domina y cuánto cuesta.
Tu texto se guarda sólo en este dispositivo.
VisuAlgoVisualizaciones animadas de estructuras de datos y algoritmos.
Comentarios
Inicia sesión para comentar.
Todavía no hay comentarios. Sé la primera persona en opinar.