Skip to content

Tema 7: Estructuras de Datos Avanzadas: Montículos (Heaps) y Colas de Prioridad

Resumen Ejecutivo

La sesión comenzó con una corrección crítica sobre el cálculo del Factor de Equilibrio en árboles AVL del tema anterior. Posteriormente, se introdujo el concepto de Montículos (Heaps) y su implementación mediante Arrays para gestionar Colas de Prioridad. Finalmente, se realizó una codificación en vivo de una Priority Queue y se dieron pautas específicas para la Actividad 2 (Árboles Binarios de Búsqueda).

Resumen Ejecutivo

La sesión comenzó con una corrección crítica sobre el cálculo del Factor de Equilibrio en árboles AVL del tema anterior. Posteriormente, se introdujo el concepto de Montículos (Heaps) y su implementación mediante Arrays para gestionar Colas de Prioridad. Finalmente, se realizó una codificación en vivo de una Priority Queue y se dieron pautas específicas para la Actividad 2 (Árboles Binarios de Búsqueda).

Conceptos Clave

Factor de Equilibrio (AVL): Diferencia entre las alturas de los subárboles (no sus factores de equilibrio). * Montículo (Heap): Árbol binario completo donde se cumple una relación de orden estricta entre padre e hijos. * Heapify: Proceso de reordenamiento ("burbujeo") hacia arriba o abajo para restaurar la propiedad del montículo tras una inserción o borrado. * Cola de Prioridad: Estructura de datos abstracta (TAD) donde el orden de salida no es FIFO, sino basado en un criterio de prioridad (máximo o mínimo).

Desarrollo del Temario

1. Corrección: Factor de Equilibrio (Tema 6 - Árboles AVL)

El profesor inició la clase rectificando un error conceptual de la sesión anterior.

  • El Error: Se estaba calculando el equilibrio restando el Factor de Equilibrio derecho menos el izquierdo.
  • La Corrección (¡IMPORTANTE!): El cálculo correcto se basa en la Altura (H).

  • Fórmula:

  • Definición de Altura: Número de niveles menos 1 (o longitud del camino más largo).

  • Nodo hoja: Altura 0.
  • Árbol vacío: Altura -1.

Ejemplo de Clase: Si el subárbol derecho tiene una altura de 1 y el izquierdo es un árbol vacío (-1), el cálculo es: 1 - (-1) = 2. Esto indica desequilibrio.

2. Montículos (Heaps)Un montículo es un árbol binario completo (lleno hasta el penúltimo nivel, y el último nivel se llena de izquierda a derecha). No sirven para búsquedas, sino para recuperar rápidamente el elemento raíz (extremo).

Tipos de Montículos1. Montículo de Máximos (Max-Heap):

  • Regla: El nodo padre siempre es mayor que sus hijos.

  • La Raíz contiene el valor máximo de la colección.

  • Montículo de Mínimos (Min-Heap):

  • Regla: El nodo padre siempre es menor que sus hijos.
  • La Raíz contiene el valor mínimo.

Operaciones Principales Inserción: Se añade el elemento en la primera posición libre (final del array/árbol) y se realiza Heapify Up* (flotar) si viola la condición del montículo.

  • Borrado: Siempre se elimina la Raíz.
  • Se guarda la raíz.
  • Se mueve el último elemento del montículo a la posición de la raíz.
  • Se realiza Heapify Down (hundir) comparando con los hijos para restaurar el orden.

3. Implementación con Arrays (¡Técnico!)Para el ejercicio práctico y el examen, es crucial saber mapear un árbol binario a un Array.

Fórmulas de Indexación (Base 0): Dado un nodo en la posición (índice) k:

  • Hijo Izquierdo:

  • Hijo Derecho:

  • Padre:

Nota del Profesor: Estas fórmulas son vitales para implementar los métodos private void swap, heapifyUp y heapifyDown requeridos en el ejercicio.

4. Colas de Prioridad (Priority Queues)Es un TAD que suele implementarse usando Montículos.

  • Lógica: No es FIFO (First In, First Out). El primero en salir es el que tiene mayor prioridad (o menor, dependiendo de la regla).
  • Desempates:
  • Si dos elementos tienen la misma prioridad, se puede usar FIFO (orden de llegada).
  • O se puede definir una segunda propiedad de prioridad (Ej: Nota global igual \to desempata nota del examen).

5. Ejercicio Práctico: IntegerPriorityQueueSe implementó en vivo una cola de prioridad de enteros basada en un Max-Heap usando un array básico.

Requisitos del Ejercicio:

Estructura: Array básico de Java (Integer[]).

Regla: A mayor valor, mayor prioridad. Se permiten repetidos.

Restricción: No usar PriorityQueue ni ArrayList de Java.

Implementación de Métodos Clave:

A. ConstructorSe debe inicializar el array con una capacidad fija y el tamaño (size) en 0.

public IntegerPriorityQueue(int capacity).

B. Enqueue (Insertar)1. Verificar si el array está lleno (size == capacity).

  1. Insertar el valor en heap[size].
  2. Llamar a heapifyUp(size) para reordenar.
  3. Incrementar size.

C. Dequeue (Extraer)1. Verificar si está vacío.

  1. Guardar la raíz (heap[0]).
  2. Mover el último elemento (heap[size-1]) a la posición 0.
  3. Decrementar size.
  4. Llamar a heapifyDown(0) para reordenar hacia abajo.

D. Auxiliares (La lógica dura) HeapifyUp (int index):*

  • Mientras index > 0 y heap[index] > heap[parent(index)]:
  • Hacer swap.

  • Actualizar index = parent.

  • HeapifyDown (int index):

  • Comparar index con hijo izquierdo y derecho.
  • Encontrar el mayor de los tres.
  • Si el mayor no es el nodo actual (index), hacer swap con el hijo mayor y llamar recursivamente (o iterativamente) a heapifyDown en la nueva posición.

6. Pautas para la Actividad 2 (Árbol Binario de Búsqueda)El profesor dio consejos finales para la entrega de la actividad:

  • Recursividad: Es obligatoria para métodos como insert, preOrder, inOrder, postOrder. Sin ella es casi imposible implementarlo limpiamente.
  • Memoria Técnica:
  • ¡OJO AL DATO!: La memoria debe incluir capturas del código seguidas de una explicación de por qué se implementó así. No basta con pegar el código; hay que comentar la lógica.
  • El código entregado (.java) debe tener comentarios internos explicativos, no estar vacío de texto.

Nombres: Respetar estrictamente los nombres de paquetes y clases indicados en el PDF.

Preguntas de Autoevaluación1. Corrección AVL: Para calcular el factor de equilibrio de un nodo, ¿debo restar los factores de equilibrio de sus hijos o sus alturas?

  1. Indexación: En un montículo implementado en un array (índice 0), si un nodo está en la posición 4, ¿en qué posición está su padre?
  2. Lógica Heap: En un Max-Heap, si inserto un valor que es mayor que su padre, ¿qué operación debo realizar para corregir el montículo?
  3. Colas de Prioridad: Si implemento una cola de urgencias médicas donde el valor 1 es "leve" y 10 es "crítico", ¿necesito un Montículo de Máximos o de Mínimos?
  4. Práctica: ¿Qué sucede con el nodo raíz cuando se ejecuta la operación dequeue() en un montículo?