Implementación del Heap Min-Max en Java

1. Introducción a Min-Max Heap en Java
2. Implementar Max-Heap con la clase PriorityQueue y Collections.reverseOrder() en Java
3. Implementar Min-Heap con la clase PriorityQueue en Java

Este artículo implementará un max-heap y un min-heap utilizando la clase PriorityQueue. También demostraremos la inserción y eliminación de los elementos del heap.

Introducción a Min-Max Heap en Java

el heap es una estructura de datos basada en árboles y forma un árbol binario completo. Los montones se representan como un array. Hay dos tipos de montones, y son el montón mínimo y el max-heap. El montón mínimo, también conocido como min-heap, tiene el valor más pequeño en su nodo raíz o en el nodo principal. De manera similar, max-heap tiene el valor más grande en el nodo raíz o en el nodo principal. Por lo tanto, la estructura de datos del montón facilita la extracción del elemento más grande y más pequeño de un array. Podemos obtener el elemento más grande y el más pequeño en O(1). La complejidad para eliminar o insertar los elementos hacia y desde el montón es O(log N).

el heap mínimo-máximo es una estructura de datos que contiene niveles mínimos y máximos alternos. El nodo raíz contiene el valor más pequeño y el siguiente nivel por debajo de él representa el valor más grande. Los valores mínimos se representan con niveles pares como 0, 2, 4. Los niveles impares como 1, 3, 5 representan los valores máximos.

Implementar Max-Heap con la clase PriorityQueue y Collections.reverseOrder() en Java

Podemos usar la clase PriorityQueue para implementar los montones en Java. La clase implementa el min-heap por defecto, y podemos usar el método reverseOrder() de Collections para implementar el max-heap. Podemos usar el método peek() para mostrar el elemento del nodo raíz en el heap. El método poll() devuelve y elimina el valor en el nodo raíz. Podemos usar el método contains() para verificar si un elemento existe en el heap.

Por ejemplo, importe todo del paquete java.util. Cree una clase MaxHeap y escriba el método main. Luego cree una instancia de la clase PriorityQueue como pq. Utilice el tipo genérico para crear la instancia Integer. Escriba Collections.reverseOrder() entre paréntesis mientras crea el objeto. Utilice el método add() para sumar cuatro valores enteros. Llame al método peek() con el objeto pq e imprímalo. Luego, use el método poll() en el objeto. A continuación, llame al método remove() con un valor 30 como parámetro y luego imprima los elementos en el array usando los métodos iterator() y hasNext(). Finalmente, utilice el método contains() con un parámetro 20.

En el siguiente ejemplo, import java.util.* Importará la clase PriorityQueue, que usamos para crear un max-heap. Agregamos los valores 1, 2, 3 y 4 al montón. El método peek() devolvió el valor 4, que es el más grande de el heap. Luego, el método poll() eliminó el número máximo, 4. Luego, usamos el método remove() para eliminar el número 3, e imprimimos los elementos restantes en el heap. Imprimió los valores 1 y 2 como ya quitamos 3 y 4. Finalmente, verificamos si el montón contiene un número 2 usando el método contains(). Devolvió true ya que existe el número en el heap. Por lo tanto, implementamos el max-heap usando la clase PriorityQueue con el uso de Collectios.reverseOrder().

Código de ejemplo:

import java.util.*;

class MaxHeap {
  public static void main(String args[]) {
    PriorityQueue<Integer> pq = new PriorityQueue<Integer>(Collections.reverseOrder());
    pq.add(1);
    pq.add(3);
    pq.add(2);
    pq.add(4);
    System.out.println("The highest value in the heap:" + pq.peek());
    pq.poll();
    pq.remove(3);
    System.out.println("after removing 3:");
    Iterator<Integer> itr = pq.iterator();
    while (itr3.hasNext()) System.out.println(itr.next());
    boolean b = pq.contains(2);
    System.out.println("Does the heap contains 2 ?" + b);
  }
}

Producción :

The highest value in the heap:4
after removing 3:
2
1
Does the heap contains 2 ?true

Implementar Min-Heap con la clase PriorityQueue en Java

La clase PriorityQueue implica el heap mínimo de forma predeterminada. Aplicamos el mismo método de implementación para min-heap que aplicamos para max-heap. Usamos los mismos métodos como peek(), remove(), poll() y contains() para realizar las mismas operaciones.

En el siguiente ejemplo, agregamos los números 1, 2, 3 y 4 en el heap. El método peek() devolvió el elemento en el nodo raíz, que es 1 como se muestra en la salida. Usamos el método poll() para eliminar el elemento del nodo raíz 1. Nuevamente eliminamos el valor 3 del montón con la función remove(). Después de eliminar estos valores, nuestro montón solo contiene los elementos 2 y 4. Finalmente, usamos el método contains() para verificar si valoramos 3 en el heap. Como ya lo eliminamos, el método devuelve un valor false. Por lo tanto, implementamos un min-heap usando la clase PriorityQueue.

Código de ejemplo:

import java.util.*;

class MinHeap {
  public static void main(String args[]) {
    PriorityQueue<Integer> pq = new PriorityQueue<Integer>();
    pq.add(1);
    pq.add(3);
    pq.add(2);
    pq.add(4);
    System.out.println("The highest value in the heap:" + pq.peek());
    pq.poll();
    pq.remove(3);
    System.out.println("after removing 3:");
    Iterator<Integer> itr = pq.iterator();
    while (itr.hasNext()) System.out.println(itr.next());
    boolean b = pq.contains(3);
    System.out.println("Does the heap contains 3 ?" + b);
  }
}

Producción :

The highest value in the heap:1
after removing 3:
2
4
Does the heap contains 2 ?false