Download Presentación de PowerPoint
Transcript
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