1) Un HEAP de n elementos puede definirse como un vector en el que sus elementos cumplen las siguientes condiciones.

Al elemento k-ésimo se lo denomina nodo padre de los elementos 2k y 2k+1. Con esto se ve que:

v[1] >= v[2] y v[3]

v[2] >= v[4] y v[5]

v[3] >= v[6] y v[7]

…

Ejemplo:

70 33 56 25 2 30 25 21

 

A partir de un HEAP es posible armar un vector ordenado. Para ello, se remueve del HEAP el primer elemento que es el mayor de vector ordenado y se reordena el HEAP para transformarlo en otro HEAP de n-1 elementos. Repitiendo el procedimiento hasta sacar a todos los elementos del HEAP se obtendría el vector ordenado.

Implementar una función ( y programa que la use) que a partir de un HEAP de SIZE elementos genere su vector ordenado.

 

 

Hint: La remoción de un elemento del HEAP causa que algunos de los nodos hijos del elemento removido pase a ocupar su lugar…