HEAP

Heap tree

@Spec Heap

Un árbol heap es un árbol binario completo que tiene
un orden impuesto en sus nodos tal que el valor de la raiz
del árbol es mayor o igual que los valores en ambos sub-árboles,
y ambos sub-árboles son a su vez árboles heap.


***Glosario:***

Árbol Completo:
	Un àrbol binario completo de altura H es un árbol que está lleno 
	hasta el nivel H-1, con el nivel H llenado de izquierda a derecha
	mas formalmente:

	es_completo(a):
		if( vacio(a) )
			return true;
		else
			if( altura(izq(a)) <= 1 && es_completo(izq(a)) && es_completo(der(a)))
				return true
			else
				return false



Para construir un árbol completo creamos un árbol lleno hasta el penultimo nivel y lo llenamos de izquierda a derecha en el último nivel. Entonces necesitamo un predicado que regrese cierto si el árbol está lleno. Un árbol está lleno si esta vacio o si las alturas de sus subárboles izq y derecho son la misma y ambos son llenos. Esto es:
	*es_lleno(Arbin a)*
	
	es_lleno(a):
		if( vacio(a) )
			return true
		else
			if( altura(izq(a)) ==  altura(der(a)) && es_lleno(izq(a)) && es_lleno(der(a)))
				return true

			return false
*haz_completo (Elem e,  Arbin a)*
```
haz_completo(Elem a, Arbin a){
	if(esvacio(a))
		return cons(e, vacio(), vacio());
	else if (( altura(izq(a)) == altura(der(a))+1 && eslleno(izq(a)) || ( altura(izq(a)) == altura(der(a)) && !eslleno(der(a)) )
	    return cons(raiz(a), izq(a), hazcompleto(e,der(a)));
	else return cons(raiz(a), hazcompleto(e, izq(a)), der(a));
}
```

*crea_heap(Arbin a)*
```
crea_heap(Arbin a){
	Si esvacio(a){
		return a
	}sino si(altura(izq(a)) - altura(der(a)) <= 1 ){
		return haz_heap(raiz(a), crea_heap(izq(a)), crea_heap(der(a)))
		
	}
}
```

*haz_heap(Elem e, Arbin i, Arbin d)*
```
haz_heap(Elem e, Arbin i, Arbin d){
	si(esvacio(i) && esvacio(d))
		retrun cons(e, vacio(), vacio())
	sino si(!esvacio(i) && esvacio(d)){
		si(e >= raiz(i)) return cons(e, i, vacio())
		sino cons(raiz(i),cons(e,vacio(),vacio()),vacio())
	}sino{
		si(e > raiz(i) && e > raiz(d)) return cons(e,i,d)
		sino si raiz(i) >= raiz(d){
			ret cons(raiz(i), haz_heap(e, izq(i), der(i), d)
		}sino{
			ret cons(raiz(d), i, haz_heap(e, izq(d), der(d))
		}
	}
}
```