HEAPS - MAX HEAP Y MIN HEAP ¿Como funcionan? Código en Java

En este post hablaremos sobre los Heaps o montículos en Java (Max Heap y Min Heap), ¿que son? ¿Cómo funcionan? ¿Cómo se programan? y también veremos el código en Java de como se implementa.

A los heaps también se les conoce en español como montículos. Este es un tema que se ve en ingeniería de software o ingeniería de sistemas en estructuras de datos.

Si hablamos de heaps o montículos es inevitable pensar en arboles, así que primero debes tener claro o al menos conocer la teoría de arboles en programación.

Es importante hacer la aclaración que todo montículo por definición es un árbol, pero no todo árbol es un montículo.

Heaps o montículos en programación

En computación, un montículo (o heap en inglés) es una estructura de datos del tipo árbol 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 cualquiera de sus nodos hijos, mientras que en los montículos mínimos, el valor del nodo padre es siempre menor al de sus nodos hijos.

¿Cuando un árbol es un montículo?

Un árbol cumple la condición de montículo si satisface dicha condición y además es un árbol binario casi 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. En un montículo de prioridad, el mayor elemento (o el menor, dependiendo de la relación de orden escogida) está siempre en el nodo raíz.

Por esta razón, los montículos son útiles para implementar colas de prioridad.

Ventajas de los montículos

Una ventaja que poseen los montículos es que, por ser árboles completos, se pueden implementar usando arreglos (arrays), lo cual simplifica su codificación y libera al programador del uso de punteros. La eficiencia de las operaciones en los montículos es crucial en diversos algoritmos de recorrido.  

Como funciona el max-heap y min-heap

En este vídeo explico detalladamente el funcionamiento.

Codigo en Java

Veamos un ejemplo sobre como es la implementación de un heap o montículo en el lenguaje de programación Java.

public class Monticulo {
	private int heap_size;
	
	
	/**
	 * @pre: A es un arreglo en la que la los hijos de la raiz son monticulos.
	 * @pos: Convierte a A en un monticulo.
	 * @param A
	 * @param i
	 */
	
	
	public void Max_Heapify (double []A, int i){
		int l = Left(i);
		int r = Right(i);
		int largest;
		if (l<= heap_size && A[l]>A[i]){
			largest=l;
		}
		else {
			largest=i;
		}
		if (r<= heap_size && A[r]>A[largest]){
			largest=r;
		}
		if (largest!=i){
			double temp = A[i];
			double temp2=A[largest];
			A[i]= temp2;
			A[largest]=temp;
			Max_Heapify(A,largest);
		}
	}
	
	public void Build_Max_Heap (double []A){
		heap_size = A.length-2;
		for (int i = (A.length-1)/2; i >=0; i--) {
			Max_Heapify(A, i);
		}
		
		
	}
	
	public void Heap_Sort (double []A){
		Build_Max_Heap(A);
		for (int i = A.length-1; i >1; i--) {
			double temp = A[0];
			double temp2=A[i];
			A[i]=temp;
			A[0]=temp2;
			heap_size=heap_size-1;
			Max_Heapify(A, 0);
		}
	}
	
	public int Parent (int i) {
		return i/2;
	}
	
	public int Left (int i) {
		return 2*i;
	}
	
	public int Right (int i) {
		return 2*i+1;
	}
	
	
	public static void main(String[] args) {
		
		double []a = {16,14,10,8,7,9,3,2,4,1};
		Monticulo b = new Monticulo();
		b.Heap_Sort(a);
		String z = "[";
		for (int i = 0; i < a.length; i++) {
			z+= a[i]+" , ";
		}
		System.out.println(z);
	}

}

Espero que te haya gustado. Si tienes alguna duda sobre el código, no dudes en dejar un comentario al final de este post.

Dentro del método Main solo esta como se usa la clase y la respuesta que imprime por consola. Puedes borrar por completo el Main y hacer las debidas invocaciones a la clase desde el lugar donde quieras hacer uso del heap o montículo.

Si quieres conocer otros artículos parecidos a HEAPS - MAX HEAP Y MIN HEAP ¿Como funcionan? Código en Java puedes visitar la categoría Java.