Repasa arreglos e índices y reconoce O(log n). Una cola FIFO no es requisito para implementar un heap.
CONTENIDO ORIGINAL
Avanza en orden. Cada lección está redactada para Palta es Cool, utiliza ejemplos propios y termina con una actividad cuya respuesta puedes desplegar.
ANTES DE EMPEZAR
Ubícate antes de avanzar
Al terminar deberías poder relacionar Heap binario con Subir y bajar y resolver un caso nuevo.
Reserva entre 35 y 55 minutos para lectura, ejemplos, tres comprobaciones y cierre.
04 / PREPARA EL LABORATORIO
Instala un JDK actual y utiliza un editor o IDE con soporte para Java. Trabaja en un proyecto de laboratorio separado.
Abrir la guía de herramientas →Diagnóstico rápido: ¿cómo se relacionan Heap binario y Subir y bajar? ＋
No necesitas acertar todavía. Escribe una hipótesis de dos líneas y compárala con tu respuesta al finalizar; si puedes corregirla y justificar el cambio, hubo aprendizaje.
Aprende el tema paso a paso
Aprenderás por qué una cola de prioridad necesita conservar solo una propiedad parcial y no ordenar todos sus elementos.
Al terminar podrás
- Una cola de prioridad atiende el extremo, no conserva un orden total visible
- Un heap binario completo cabe en un arreglo
- Insertar sube; eliminar la raíz baja
01
Prioridad
Una cola de prioridad atiende el extremo, no conserva un orden total visible
Cada elemento tiene una prioridad y remove entrega la prioridad máxima o mínima según el contrato. Los elementos con la misma prioridad requieren una regla explícita si el orden de llegada importa. Un heap permite consultar el extremo en O(1) e insertar o retirar en O(log n).
Define si menor o mayor número significa más prioridad.
Los empates no son automáticamente FIFO.
Ordenar toda la colección en cada inserción hace trabajo innecesario.
¿Una PriorityQueue permite recorrer todos los elementos ya ordenados?
Mostrar respuesta ＋
No debe asumirse. Garantiza el elemento del extremo al retirarlo; su iterador no representa necesariamente el orden de prioridad.
02
Representación
Un heap binario completo cabe en un arreglo
En índices desde cero, los hijos de i están en 2i + 1 y 2i + 2; el padre en (i - 1) / 2. La forma completa evita guardar enlaces. En un max-heap, cada padre tiene prioridad mayor o igual que sus hijos.
La forma del árbol depende solo de size.
La propiedad se comprueba entre padres e hijos.
Un heap no es un árbol binario de búsqueda.
¿Por qué buscar una clave cualquiera sigue siendo O(n)?
Mostrar respuesta ＋
Porque la propiedad del heap solo ordena verticalmente padres e hijos; no indica en qué rama está una clave arbitraria.
03
Restaurar el invariante
Insertar sube; eliminar la raíz baja
Al insertar se agrega al final para conservar la forma y se intercambia con su padre mientras viole la propiedad. Al retirar se mueve el último a la raíz y se intercambia con el hijo apropiado. Deben comprobarse vacío, capacidad e índices antes de acceder.
Sift-up recorre como máximo la altura.
Sift-down elige el hijo de mayor prioridad en max-heap.
Altura de un heap completo: O(log n).
¿Qué hijo debe elegirse al bajar en un max-heap?
Mostrar respuesta ＋
El hijo con mayor prioridad; cambiar con el menor podría dejar todavía violada la relación con el otro hijo.
Tu recorrido en tres ideas
- Una cola de prioridad atiende el extremo, no conserva un orden total visible
- Un heap binario completo cabe en un arreglo
- Insertar sube; eliminar la raíz baja
CIERRE DE LA SECCIÓN
Comprueba que puedes usarlo
Antes de continuar, revisa estos tropiezos frecuentes y resuelve un caso sin copiar los ejemplos.
Creer que todo el arreglo del heap está ordenado.
Bajar intercambiando con un hijo sin comparar ambos.
Ahora hazlo sin guía
Construye una agenda de tareas con prioridad y orden estable para empates.
Mostrar pauta de corrección ＋
Una respuesta sólida:
- Preserva forma completa y propiedad del heap.
- Prueba prioridades repetidas.
- Justifica O(log n) para agregar y retirar.