Implementar Heap Min-Max em Java

1. Introdução ao Min-Max Heap em Java
2. Implementar Max-Heap com a classe PriorityQueue e Collections.reverseOrder() em Java
3. Implementar Min-Heap com a classe PriorityQueue em Java

Este artigo implementará um heap máximo e um heap mínimo usando a classe PriorityQueue. Também demonstraremos a inserção e exclusão dos elementos do heap.

Introdução ao Min-Max Heap em Java

Um heap é uma estrutura de dados baseada em árvores e forma uma árvore binária completa. Heaps são representados como um array. Existem dois tipos de heap e são heap mínimo e heap máximo. O heap mínimo, também conhecido como heap mínimo, tem o menor valor em seu nó raiz ou no nó pai. Da mesma forma, o heap máximo tem o maior valor no nó raiz ou no nó pai. Portanto, a estrutura de dados do heap torna mais fácil extrair o maior e o menor elemento de um array. Podemos obter o maior e o menor elemento em O(1). A complexidade para remover ou inserir os elementos de e para a pilha é O(log N).

Um heap mín-máx é uma estrutura de dados que contém níveis mínimos e máximos alternados. O nó raiz contém o menor valor e o próximo nível abaixo dele representa o maior valor. Os valores mínimos são representados com níveis pares como 0, 2, 4. Os níveis ímpares como 1, 3, 5 representam os valores máximos.

Implementar Max-Heap com a classe PriorityQueue e Collections.reverseOrder() em Java

Podemos usar a classe PriorityQueue para implementar os heaps em Java. A classe implementa o heap mínimo por padrão e podemos usar o método reverseOrder() de Coleções para implementar o heap máximo. Podemos usar o método peek() para exibir o elemento do nó raiz em um heap. O método poll() retorna e remove o valor no nó raiz. Podemos usar o método contains() para verificar se um elemento existe em um heap.

Por exemplo, importe tudo do pacote java.util. Crie uma classe MaxHeap e escreva o método main. Em seguida, crie uma instância da classe PriorityQueue como pq. Use o tipo genérico para criar a instância Integer. Escreva Collections.reverseOrder() entre parênteses ao criar o objeto. Use o método add() para adicionar quatro valores inteiros. Chame o método peek() com o objeto pq e imprima-o. Então, use o método poll() no objeto. Em seguida, chame o método remove() com um valor 30 como o parâmetro e, em seguida, imprima os elementos na matriz usando os métodos iterator() e hasNext(). Finalmente, use o método contains() com um parâmetro 20.

No exemplo abaixo, o import java.util.* irá importar a classe PriorityQueue, que usamos para criar um heap máximo. Adicionamos os valores 1, 2, 3 e 4 à pilha. O método peek() retornou o valor 4, que é o maior em um heap. Então, o método poll() removeu o número máximo, 4. Em seguida, usamos o método remove() para remover o número 3 e imprimimos os elementos restantes em uma pilha. Ele imprimiu os valores 1 e 2, pois já removemos 3 e 4. Finalmente, verificamos se o heap contém um número 2 usando o método contains(). Ele retornou true, pois existe o número em uma pilha. Assim, implementamos o heap máximo usando a classe PriorityQueue com o uso de Collectios.reverseOrder().

Código de exemplo:

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);
  }
}

Produção:

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

Implementar Min-Heap com a classe PriorityQueue em Java

A classe PriorityQueue implementa min heap por padrão. Aplicamos o mesmo método de implementação para o heap mínimo que aplicamos para o heap máximo. Usamos os mesmos métodos como peek(), remove(), poll() e contains() para realizar as mesmas operações.

No exemplo abaixo, adicionamos os números 1, 2, 3 e 4 em uma pilha. O método peek() retornou o elemento no nó raiz, que é 1 conforme mostrado na saída. Usamos o método poll() para remover o elemento do nó raiz 1. Novamente removemos o valor 3 do heap com a função remove(). Depois de remover esses valores, nosso heap contém apenas os elementos 2 e 4. Finalmente, usamos o método contains() para verificar se valorizamos 3 em um heap. Como já o removemos, o método retorna um valor false. Assim, implementamos um min-heap usando a classe PriorityQueue.

Código de exemplo:

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);
  }
}

Produção:

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