Implementar min-heap em Java
- Implementação de Min Heap sem usar biblioteca em Java
-
Implementação de Min-Heap usando
PriorityQueueem Java
Um Heap mínimo é um Heap em que cada nó interno é menor ou igual aos valores de seus filhos. Veremos como implementar Min Heap com e sem o uso de uma biblioteca nos pontos a seguir.
Implementação de Min Heap sem usar biblioteca em Java
Neste exemplo, vemos a implementação sem usar nenhuma biblioteca. Aqui criamos uma classe JavaMinHeap na qual criamos três variáveis de instância HeapArray é um array de tipo int que manterá todos os valores do heap, size é o tamanho do heap, maxSize armazena o tamanho máximo do HeapArray. Também criamos uma variável estática FRONT do tipo int e a inicializamos com 1.
Obtemos maxSize como um parâmetro no construtor e o armazenamos na variável de instância maxSize. Inicializamos size com 0 e HeapArray com um array int com o tamanho maxSize + 1. Armazenamos o valor mínimo de Integer no primeiro índice de HeapArray.
Agora criamos métodos para realizar operações no heap. A função parent() assume uma position como parâmetro e retorna o pai da posição passada do nó. Então criamos leftChild() que retorna o filho esquerdo da posição recebida como parâmetro. O mesmo vale para a criança certa usando rightChild() que retorna o valor do nó (2 * posição) + 1.
isLeaf() verifica se um nó é um nó folha ou não, o que significa que ele tem algum filho. swapNodes() é um método que troca o valor do nó da posição fpos com a posição spos. No método, criamos uma variável temp e a inicializamos, a posição fpos de HeapArray e armazenamos o valor spos de HeapArray em HeapArray[fpos]. Agora armazenamos o valor temp em HeapArray[spos].
convertToMinHeap() verifica se a posição recebida como parâmetro é uma folha ou não usando isLeaf e, se não, verifica se o valor atual na posição de HeapArray é maior que o filho esquerdo ou direito. Então verificamos se o filho esquerdo é menor que o filho direito e, se for, usamos swapNodes() para trocar os nós e passar a position e o filho esquerdo a position. Nós convertemos novamente o filho esquerdo recebido em min heap usando convertToMinHeap().
Usamos insert() para inserir os valores no min-heap. Em insert() retornamos sem inserir se o array atingiu maxSize; caso contrário, obtemos a posição em ++size e inserimos o elemento recebido em HeapArray[++size]. Colocamos size em current. Criamos um loop e trocamos nós se o elemento na posição current for menor que seu pai.
Para imprimir o min-heap, criamos printheap() e percorremos o HeapArray onde o pai está na posição i, o filho esquerdo está na posição 2 * i e o filho direito está na posição 2 * i + 1. Na função main(), usamos insert() para inserir elementos na pilha.
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();
}
}
Produção:
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
Implementação de Min-Heap usando PriorityQueue em Java
Neste programa, usamos PriorityQueue que é usado para criar heaps máximos e mínimos. PriorityQueue fornece múltiplos como add() que insere o elemento na fila, peek() busca o cabeçalho da fila e o remove, poll() também recupera o cabeçalho da fila, mas sem removê-lo . contains() verifica se o elemento especificado é a fila. remove() remove o elemento especificado.
Combinamos todas as funções de PriorityQueue para criar e realizar operações min-heap. Primeiro, criamos um objeto priorityQueue vazio do tipo Integer usando new PriorityQueue(). Em seguida, adicionamos nossos elementos usando o método add(). Para imprimir e remover o cabeçote da fila, chamamos priorityQueue.peek() que imprime 10. Em seguida, imprimimos todos os elementos da fila usando for aprimorado. Agora chamamos poll() que imprime e remove 10. Em seguida, removemos um elemento da fila. Usamos contains() que retorna um booleano para verificar se um elemento está na fila. Por fim, para imprimir o valor restante, convertemos a fila em um 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());
}
}
Produção:
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
Rupam Saini is an android developer, who also works sometimes as a web developer., He likes to read books and write about various things.
LinkedIn