Ordenamiento heap-sort

Ordenamiento Heap-Sort
Los métodos sencillos de ordenamiento por lo general requieren de aproximadamente n x n pasos para ordenar un array de n elementos.

Ordenamiento Heap-Sort
► Elordenamiento puede efectuarse moviendo los registros con las claves. Una alternativa es el crear una tabla de referencias a los registros y mover las referencias y no los datos.

Ordenamiento Heap-Sort
►La estructura de datos “heap” es un arreglo de objetos que pueden ser vistos como un árbol binario completo (sólo pueden faltar nodos al final del último nivel). Ej
16 14 8 2 4 7 1 9

1
10 32

3

4

5

6

7

8

9

10

16 |14 |10 | 8 | 7 | 9 | 3 | 2 | 4 | 1

► ► ►

Inicialmente Heap-Sort creará un heap a partir de un arreglo arbitrario. La idea principal seráaprovechar el hecho de que en el heap, el elemento de mayor valor se encuentra en la raíz. Dada la condición anterior del heap, podemos insertar este elemento directamente donde le corresponde en elarreglo, o sea, al final.

Ordenamiento Heap-Sort
La idea general es reemplazar el elemento mayor por el ultimo en el arreglo y luego arreglar un posible problema que haya quedado en la raíz, suponiendoahora que el heap tiene un elemento menos, para posteriormente repetir el proceso. Siguiendo estas ideas, el código de Heap-Sort es:
Heapsort(A) Build_Heap(A) for (i= lenght(A) downto 2 ) doexchange A[1] A[i] heap_size [A] = heap_size [A]-1 Heapify(A,1)

Ordenamiento Heap-Sort

Ordenamiento Heap-Sort
►Construir

un heap invocando a Build_Heap

La construcción del heap se lograaplicando la función heapify de manera de cubrir el arreglo desde abajo hacia arriba El procedimiento Build_Heap cuyo costo toma O(n) va a través de los nodos restantes y corre heapify en cada uno.Build_Heap(A) { heap_size [A] = length [A] for i = length(A) /2  downto 1 do Heapify(A,i) }

Ordenamiento Heap-Sort
►Tiempo

de ejecución Heapify

En un subárbol de tamaño n, con raíz en el...