Implementar min-heap en Java

1. Implementación de Min Heap sin usar la biblioteca en Java
2. Implementación de Min-Heap usando PriorityQueue en Java

Un montón mínimo es un montón en el que cada nodo interno es más pequeño o igual que los valores de sus hijos. Veremos cómo implementar Min Heap con y sin usar una biblioteca en los siguientes puntos.

Implementación de Min Heap sin usar la biblioteca en Java

En este ejemplo, vemos la implementación sin usar ninguna biblioteca. Aquí creamos una clase JavaMinHeap en la que creamos tres variables de instancia. HeapArray es un array de tipo int que mantendrá todos los valores del montón, size es el tamaño del montón, maxSize almacena el tamaño máximo del HeapArray. También creamos una variable estática de tipo int y la inicializamos con 1.

Obtenemos maxSize como parámetro en el constructor y lo almacenamos en la variable de instancia maxSize. Inicializamos size con 0 y HeapArray con un array de int con el tamaño de maxSize + 1. Almacenamos el valor mínimo de Integer en el primer índice de HeapArray.

Ahora creamos métodos para realizar operaciones en el montón. La función parent() toma una posición como parámetro y devuelve el padre de la posición pasada del nodo. Luego creamos leftChild() que devuelve el hijo izquierdo de la posición recibida como parámetro. Lo mismo ocurre con el niño derecho que usa rightChild() que devuelve el valor del nodo (2 * posición) + 1.

isLeaf() comprueba si un nodo es un nodo hoja o no, lo que significa que tiene algún hijo. swapNodes() es un método que intercambia el valor del nodo de la posición fpos con la posición spos. En el método, creamos una variable temp y la inicializamos, la posición fpos de HeapArray y almacenamos el valor spos de HeapArray en HeapArray[fpos]. Ahora almacenamos el valor temp en HeapArray[spos].

convertToMinHeap() comprueba si la posición recibida como parámetro es una hoja o no usa isLeaf y, si no es así, comprueba si el valor actual en la posición de HeapArray es mayor que el hijo izquierdo o el hijo derecho. Luego verificamos si el hijo de la izquierda es más pequeño que el hijo de la derecha, y si lo es, usamos swapNodes() para intercambiar los nodos y pasar la posición y el hijo de la izquierda en la posición. Volvemos a convertir el hijo izquierdo recibido en un montón mínimo usando convertToMinHeap().

Usamos insert() para insertar los valores en el min-heap. En insert() volvemos sin insertar si el array alcanzó maxSize; si no, obtenemos la posición en ++size e insertamos el elemento recibido en HeapArray[++size]. Ponemos size a actual. Creamos un bucle e intercambiamos nodos si el elemento en la posición actual es más pequeño que su padre.

Para imprimir el min-heap, creamos printheap() y recorremos el HeapArray donde el padre está en la posición i-ésima, el hijo izquierdo está en la posición 2 * i y el hijo derecho está en la posición 2 * i + 1. En la función main(), usamos insert() para insertar elementos en el montón.

public class JavaMinHeap {
  private final int[] HeapArray;
  private int size;
  private final int maxsize;

  private static final int FRONT = 1;

  public JavaMinHeap(int maxsize) {
    this.maxsize = maxsize;
    this.size = 0;
    HeapArray = new int[this.maxsize + 1];
    HeapArray[0] = Integer.MIN_VALUE;
  }

  private int parent(int position) {
    return position / 2;
  }

  private int leftChild(int position) {
    return (2 * position);
  }

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

  private boolean isLeaf(int position) {
    if (position >= (size / 2) && position <= size) {
      return true;
    }
    return false;
  }

  private void swapNodes(int fpos, int spos) {
    int temp;
    temp = HeapArray[fpos];
    HeapArray[fpos] = HeapArray[spos];
    HeapArray[spos] = temp;
  }

  private void convertToMinHeap(int position) {
    if (!isLeaf(position)) {
      if (HeapArray[position] > HeapArray[leftChild(position)]
          || HeapArray[position] > HeapArray[rightChild(position)]) {
        if (HeapArray[leftChild(position)] < HeapArray[rightChild(position)]) {
          swapNodes(position, leftChild(position));
          convertToMinHeap(leftChild(position));
        } else {
          swapNodes(position, rightChild(position));
          convertToMinHeap(rightChild(position));
        }
      }
    }
  }

  public void insert(int element) {
    if (size >= maxsize) {
      return;
    }
    HeapArray[++size] = element;
    int current = size;

    while (HeapArray[current] < HeapArray[parent(current)]) {
      swapNodes(current, parent(current));
      current = parent(current);
    }
  }

  public void printHeap() {
    for (int i = 1; i <= size / 2; i++) {
      System.out.println("PARENT : " + HeapArray[i]);

      System.out.println("--LEFT CHILD : " + HeapArray[2 * i]);

      System.out.println("--RIGHT CHILD : " + HeapArray[2 * i + 1]);
      System.out.println();
    }
  }

  public static void main(String[] arg) {
    System.out.println("The Min Heap is ");
    JavaMinHeap minHeap = new JavaMinHeap(10);
    minHeap.insert(10);
    minHeap.insert(2);
    minHeap.insert(7);
    minHeap.insert(15);
    minHeap.insert(90);
    minHeap.insert(19);
    minHeap.insert(8);
    minHeap.insert(22);
    minHeap.insert(9);

    minHeap.printHeap();
  }
}

Producción :

The Min Heap is 
PARENT : 2
--LEFT CHILD : 9
--RIGHT CHILD : 7

PARENT : 9
--LEFT CHILD : 10
--RIGHT CHILD : 90

PARENT : 7
--LEFT CHILD : 19
--RIGHT CHILD : 8

PARENT : 10
--LEFT CHILD : 22
--RIGHT CHILD : 15

Implementación de Min-Heap usando PriorityQueue en Java

En este programa, usamos PriorityQueue que se utiliza para crear montones máximos y mínimos. PriorityQueue proporciona múltiples como add() que inserta el elemento en la cola, peek() recupera el encabezado de la cola y lo elimina, poll() también recupera el encabezado de la cola pero sin eliminarlo . contains() comprueba que el elemento especificado es la cola. remove() elimina el elemento especificado.

Combinamos todas las funciones de PriorityQueue para crear y realizar operaciones min-heap. Primero creamos un objeto priorityQueue vacío de tipo Integer usando new PriorityQueue(). Luego agregamos nuestros elementos usando el método add(). Para imprimir y eliminar el encabezado de la cola, llamamos a priorityQueue.peek() que imprime 10. Luego imprimimos todos los elementos de la cola usando el mejorado for. Ahora llamamos a poll() que imprime y elimina 10. Luego eliminamos un elemento de la cola. Usamos contains() que devuelve un booleano para comprobar si un elemento está en la cola. Por último, para imprimir el valor restante, convertimos la cola en un array usando toArray().

import java.util.*;

public class JavaMinHeap {
  public static void main(String[] args) {
    PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();

    priorityQueue.add(10);
    priorityQueue.add(15);
    priorityQueue.add(25);
    priorityQueue.add(200);

    System.out.println("The head value using peek(): " + priorityQueue.peek());

    System.out.println("The queue elements: ");
    for (Integer integer : priorityQueue) System.out.println(integer);

    priorityQueue.poll();
    System.out.println("After removing the head element using poll(): ");
    for (Integer integer : priorityQueue) System.out.println(integer);

    priorityQueue.remove(25);
    System.out.println("After removing 25 with remove(): ");
    for (Integer integer : priorityQueue) System.out.println(integer);

    boolean b = priorityQueue.contains(15);
    System.out.println("Check if priorityQueue contains 15 using contains():  " + b);

    Object[] arr = priorityQueue.toArray();
    System.out.println("Values in array: ");
    for (Object o : arr) System.out.println("Value: " + o.toString());
  }
}

Producción :

The head value using peek(): 10
The queue elements: 
10
15
25
200
After removing the head element using poll(): 
15
200
25
After removing 25 with remove(): 
15
200
Check if priorityQueue contains 15 using contains():  true
Values in array: 
Value: 15
Value: 200