Traza de Heap Sort y construccion de monticulo

Enunciado

Dado el siguiente arreglo:

$A = [4, 10, 3, 5, 1, 8, 7, 2, 9, 6]$

El algoritmo Heap Sort funciona en dos fases: (1) construir un max-heap, (2) extraer repetidamente el maximo.

Fase 1: Construccion del Max-Heap

(a) Represente el arreglo como un arbol binario completo. Recuerde que para un nodo en la posicion $i$ (indexado desde 0):

• Hijo izquierdo: $2i + 1$
• Hijo derecho: $2i + 2$
• Padre: $\lfloor (i-1)/2 \rfloor$

(b) Aplique el procedimiento Build-Max-Heap (ejecutar heapify desde el ultimo nodo interno hacia la raiz). Muestre el arreglo despues de cada llamada a heapify.

Fase 2: Extraccion y ordenamiento

(c) Una vez construido el max-heap, realice las tres primeras extracciones del maximo:

1. Intercambie la raiz con el ultimo elemento del heap.
2. Reduzca el tamano del heap en 1.
3. Ejecute heapify en la raiz.

Muestre el estado del arreglo despues de cada extraccion.

Analisis

(d) Cual es la complejidad de Build-Max-Heap? Aunque parece ser $O(n \log n)$ (ejecutar $n/2$ veces heapify con costo $O(\log n)$ cada una), demuestre intuitivamente por que en realidad es $O(n)$.

(e) Cual es la complejidad total de Heap Sort? Es estable? Es in-place? Justifique cada respuesta.

(f) Compare Heap Sort con Quick Sort y Merge Sort completando la siguiente tabla:

Criterio	Quick Sort	Merge Sort	Heap Sort
Mejor caso
Peor caso
Estable?
In-place?
Espacio extra