Download Presentación de PowerPoint

El montículo es una estructura de datos del tipo árbol binario con información
perteneciente a un conjunto ordenado.
Los montículos máximos tienen la característica de que cada nodo padre tiene un
valor mayor que el de todos sus nodos hijos, mientras que en los montículos
mínimos, el valor del nodo padre es siempre menor al de sus nodos hijos.
Un árbol cumple la condición de montículo si satisface dicha condición y además
es un árbol binario completo. Un árbol binario es completo cuando todos los
niveles están llenos, con la excepción del último, que se llena desde la izquierda
hacia la derecha.
Procedimiento:
1. Se toman uno a uno los datos a ordenar, y se
insertan el montículo (tipo máximo), de tal
manera que se preserven sus características.
2. Se retira el primer elemento del montículo y se
ubica en la última posición de la estructura de
resultados.
3. Se reorganiza el montículo sin su primer
elemento.
4. Se repite desde el paso 2, hasta obtener un
montículo vacío o sin elementos.
void ord_monticulo(int vector[], long int n)
{
long int i, max;
int *temp;
max = 2*n+5;
temp=(int *)malloc(sizeof(int)*max);
for (i=0; i<max; i++)
temp[i]=-1;
for (i=0; i<n; i++)
undir(temp, 1, vector[i], max);
for (i=n-1; i>=0; i--)
{
vector[i]=temp[1];
eliminar(temp, 1, max);
}
}
Creación del arreglo,
del heap
Mete cada elemento
en el heap
Saca el primer elemento
del heap (cabeza), y lo
pasa al arreglo
void undir(int vector[], long int raiz, int valor, long int max)
{
int temp;
if (raiz >= max)
{
printf("\nerror de tamaño al undir %d",raiz); return;
}
if (vector[raiz]== -1)
vector[raiz]=valor;
else
{
if (vector[raiz]<valor)
{
temp=vector[raiz];
vector[raiz]=valor;
undir(vector, raiz, temp, max);
}
else
if(vacioder(vector,raiz, max))
undir(vector, hijoder(raiz),valor, max);
else
if(vacioizq(vector,raiz,max))
undir(vector, hijoizq(raiz),valor, max);
else
if (altura(vector, hijoizq(raiz),max) > altura(vector, hijoder(raiz), max))
undir(vector, hijoder(raiz),valor,max);
else
undir(vector, hijoizq(raiz),valor,max);
}
}
Inserta un elemento en
el heap, manteniendo
las características del
mismo
void eliminar(int vector[], long int raiz, long int max)
{
if (vector[raiz]!=-1)
{
if (hoja(vector,raiz, max))
vector[raiz]= -1;
else
if(vacioder(vector,raiz,max))
{
vector[raiz]=vector[hijoizq(raiz)];
eliminar(vector, hijoizq(raiz),max);
}
else
if(vacioizq(vector,raiz, max))
{
vector[raiz]=vector[hijoder(raiz)];
eliminar(vector, hijoder(raiz), max);
}
else
if (vector[hijoizq(raiz)]>vector[hijoder(raiz)])
{
vector[raiz]=vector[hijoizq(raiz)];
eliminar(vector, hijoizq(raiz),max);
}
else
{
vector[raiz]=vector[hijoder(raiz)];
eliminar(vector, hijoder(raiz),max);
}
}
}
Elimina la cabeza del
heap o primer
elemento (y mayor),
manteniendo las
característica del
mismo