Min Heap en Java con ejemplos

Antes de comenzar, se supone que conoce un árbol binario (en un árbol binario, cada nodo almacena una clave mayor que todas las claves en su subárbol izquierdo y menor que todas las claves en su subárbol derecho ) . Mientras que un montón binario es un árbol binario completo que satisface la propiedad de ordenación del montón mínimo o máximo.. Si no está familiarizado con estos conceptos, le recomendamos que los comprenda como requisito previo. Muchos programadores novatos pueden tener problemas con el concepto de montones, montones mínimos y colas de prioridad. En esta publicación, profundizaremos para ver en qué se diferencian los montones de los montones mínimos y cómo podemos usar colas prioritarias para implementar montones mínimos.

¿Qué es un montón mínimo?

Un montón mínimo tiene la propiedad de que cada nodo en el nivel 'n' almacena un valor que es menor o igual que el de sus hijos en el nivel 'n+1'. Debido a que la raíz tiene un valor menor o igual que sus hijos, que a su vez tienen valores menores o iguales a sus hijos, la raíz almacena el mínimo de todos los valores en el árbol.

Ejemplo

Figura 1: un montón mínimo simple Tenga en cuenta que no existe una relación necesaria entre el valor de un nodo y el de su hermano en el montón mínimo o en el montón máximo. Por ejemplo, es posible que los valores de todos los nodos del subárbol izquierdo de la raíz sean mayores que los valores de cada nodo del subárbol derecho. Figura 2: Montón mínimo con nodos secundarios izquierdos > nodos secundarios derechos

Representación de Min Heap en Java

La estructura de datos más utilizada para representar un montón mínimo es una matriz simple. Como principiante, no necesita confundir una "matriz" con un "min-heap". Puede verlo como si los valores de los nodos/elementos de un montón mínimo se almacenaran en una matriz . Al igual que no tenemos ninguna estructura de datos para almacenar un " árbol " en Java y construimos un "nodo" para él, o la forma en que usamos "mapa" para almacenar un " gráfico ". Figura 3: Representación de matriz del Montón en la Figura 2 Vamos a demostrar cómo puede simplemente acceder a los nodos principal, secundario derecho o izquierdo utilizando las siguientes fórmulas.

• Sea minHeap[] una matriz de enteros con raíz en el índice “ i = 0; ”.
• minHeap[(i - 1) / 2] devuelve el nodo principal.
• minHeap[(i * 2) + 2] devuelve el nodo secundario correcto.
• minHeap[(i * 2) + 1] devuelve el nodo secundario izquierdo.

Teniendo en cuenta la Figura n.º 2 anterior, el valor de raíz (padre) = 3, el nodo secundario izquierdo es 13 y el nodo secundario derecho = 7.

Implementación de Min Heap en Java: uso de matrices

Veamos la implementación básica de Heaps usando matriz, con índice como la posición actual del elemento que se agregará y tamaño como el tamaño total de la matriz.

import java.util.Arrays;
public class MinHeap 
{
	private int[] Heap;
	private int index;
	private int size;

	public MinHeap(int size) {
		this.size = size;
		this.index = 0;
		Heap = new int[size];
	}

	private int parent(int i) {
		return (i - 1) / 2;
	}

	private int leftChild(int i) {
		return (i * 2) + 1;
	}

	private int rightChild(int i) {
		return (i * 2) + 2;
	}

	private boolean isLeaf(int i) {
		if (rightChild(i) >= size || leftChild(i) >= size) {
			return true;
		}
		return false;
	}

	public void insert(int element) {
		if (index >= size) {
			return;
		}
		Heap[index] = element;
		int current = index;

		while (Heap[current] < Heap[parent(current)]) {
			swap(current, parent(current));
			current = parent(current);
		}
		index++;
	}

	// removes and returns the minimum element from the heap
	public int remove() {
     // since its a min heap, so root = minimum
		int popped = Heap[0]; 
		Heap[0] = Heap[--index];
		minHeapify(0);
		return popped;
	}

	// heapify the node at i
	private void minHeapify(int i) {
	// If the node is a non-leaf node and any of its child is smaller
		if (!isLeaf(i)) {
			if (Heap[i] > Heap[leftChild(i)] || 
                  Heap[i] > Heap[rightChild(i)]) {
				if (Heap[leftChild(i)] < Heap[rightChild(i)]) {
					swap(i, leftChild(i));
					minHeapify(leftChild(i));
				} else {
					swap(i, rightChild(i));
					minHeapify(rightChild(i));
				}
			}
		}
	}

	// builds the min-heap using the minHeapify
	public void minHeap() {
		for (int i = (index - 1 / 2); i >= 1; i--) {
			minHeapify(i);
		}
	}

     // Function to print the contents of the heap
	public void printHeap() {
		for (int i = 0; i < (index / 2); i++) {
			System.out.print("Parent : " + Heap[i]);
			if (leftChild(i) < index)
				System.out.print(" Left : " + Heap[leftChild(i)]);
			if (rightChild(i) < index)
				System.out.print(" Right :" + Heap[rightChild(i)]);
			System.out.println();
		}
	}
	// swaps two nodes of the heap
	private void swap(int x, int y) {
		int tmp;
		tmp = Heap[x];
		Heap[x] = Heap[y];
		Heap[y] = tmp;
	}
	public static void main(String[] arg) 
      {
	    MinHeap minHeap = new MinHeap(7);
	    minHeap.insert(3);
	    minHeap.insert(13);
	    minHeap.insert(7);
          minHeap.insert(16);
	    minHeap.insert(21);
	    minHeap.insert(12);
	    minHeap.insert(9);
	    minHeap.minHeap();

	   System.out.println("The Min Heap is : " + Arrays.toString(minHeap.Heap);
	   minHeap.printHeap();
	   System.out.println("\nThe Min Value is : " + minHeap.remove());
	   System.out.println("\nThe Min Heap is :"+ Arrays.toString(minHeap.Heap));
	   minHeap.printHeap();
	}
}

Producción

Colas de prioridad

Una cola de prioridad es un tipo especial de cola en la que cada elemento está asociado con una prioridad y se coloca de acuerdo con su prioridad. Para una implementación más sencilla del almacenamiento dinámico mínimo, usamos la clase PriorityQueue java.util.PriorityQueue proporcionada por Java. Si se supone que los elementos dados deben ordenarse/colocarse en una prioridad, se utiliza una cola de prioridad. Una Cola prioritaria es diferente de una Cola simple porque las colas estándar siguen el algoritmo Primero en entrar, primero en salir ( FIFO ), pero a veces los elementos de la cola deben procesarse de acuerdo con la prioridad, por eso se diseña la Cola prioritaria. Cuando agrega elementos a una cola de prioridad, se crea un montón mínimo de forma predeterminada.

Operaciones Comunes

Antes de pasar a la implementación, aquí hay algunas operaciones comunes en java.util.PriorityQueue que necesita saber.

• add(int elemento) inserta el elemento especificado en una cola de prioridad.
• remove(int element) elimina una única instancia del elemento especificado de esta cola, si está presente.
• peek() recupera, pero no elimina, el encabezado de esta cola, o devuelve un valor nulo si la cola está vacía.
• poll() recupera y elimina el encabezado de esta cola, o devuelve un valor nulo si esta cola está vacía.
• contiene () devuelve "verdadero" si esta cola contiene el elemento especificado.
• size() devuelve el número de elementos en esta cola/minheap de prioridad.

Implementación de Min Heap en Java usando Priority Queues

Así es como puede implementar un montón mínimo usando la clase de cola de prioridad de Java.

import java.util.*;

class MinHeapPriorityQueue {

	static PriorityQueue minHeap = new PriorityQueue();

	public static void view() {
		for (Integer x : minHeap) {
			System.out.print(x + " ");
		}
		System.out.println();
	}

	public static void main(String args[]) {
		// using "add" operation to insert elements
		minHeap.add(3);
		System.out.print("minHeap.add(3) = ");
		view();
		minHeap.add(13);
		minHeap.add(7);
		minHeap.add(16);
		minHeap.add(21);
		minHeap.add(12);
		minHeap.add(9);

		// printing Min-Heap
		System.out.print("minHeap.view() = ");
		view();

		// using "peek" method to view the head
		System.out.println("minHeap.peek() = " + minHeap.peek());

		// using "poll" method to remove and retrieve the head
		minHeap.poll();
		System.out.print("minHeap.poll() = ");
		view();

		// using "remove" method to remove specified element
		minHeap.remove(7);
		System.out.print("minHeap.remove(7) = ");
		view();

		// Check if an element is present using contains()
		boolean elementFound = minHeap.contains(11);
		System.out.println("minHeap.contains(11) = " + elementFound);
		elementFound = minHeap.contains(16);
		System.out.println("minHeap.contains(16) = " + elementFound);
	}
}

Producción

Conclusión

Los montones mínimos se usan ampliamente para recuperar el elemento más pequeño en un grupo de elementos en tiempo constante. Hay muchas otras aplicaciones de esta estructura de datos, sin embargo, puede elegir cualquier método para implementar esto. No hace falta decir que tienes que practicar con paciencia para ser bueno en eso. ¡Así que pongamos nuestros músculos en movimiento y manos a la obra!