Min Heap em Java com exemplos

Antes de começarmos, supõe-se que você conheça uma Árvore Binária (em uma árvore binária, cada nó armazena uma chave maior que todas as chaves em sua subárvore esquerda e menor que todas as chaves em sua subárvore direita ) . Considerando que, um heap binário é uma árvore binária completa que satisfaz a propriedade de ordenação de heap mínimo ou heap máximo. Se você não estiver familiarizado com esses conceitos, recomendamos que os entenda como um pré-requisito. Muitos programadores novatos podem lutar com o conceito de Heaps, Min Heaps e Priority Queues. Neste post, vamos nos aprofundar para ver como os heaps são diferentes dos Min-Heaps e como podemos usar Priority Queues para implementar Min Heaps.

O que é uma pilha mínima?

Um min-heap tem a propriedade de que cada nó no nível 'n' armazena um valor menor ou igual ao de seus filhos no nível 'n+1'. Como a raiz tem um valor menor ou igual a seus filhos, que por sua vez têm valores menores ou iguais a seus filhos, a raiz armazena o mínimo de todos os valores na árvore.

Exemplo

Figura 1: uma pilha mínima simples Observe que não há relação necessária entre o valor de um nó e o de seu irmão no heap mínimo ou no heap máximo. Por exemplo, é possível que os valores de todos os nós da subárvore esquerda da raiz sejam maiores que os valores de cada nó da subárvore direita. Figura 2: pilha mínima com nós filhos esquerdos > nós filhos direitos

Representação do Min Heap em Java

A estrutura de dados mais comumente usada para representar um Min Heap é um Array simples. Como iniciante, você não precisa confundir um “array” com um “min-heap”. Você pode ver como os valores dos nós/elementos de um heap mínimo são armazenados em um array . Assim como não temos nenhuma estrutura de dados para armazenar uma “ árvore ” em Java e construímos um “nó” para ela, ou a forma como usamos o “mapa” para armazenar um “ grafo ”. Figura 3: Representação de matriz do Heap na Figura 2 Vamos demonstrar como você pode simplesmente acessar os nós pai, filho direito ou esquerdo usando as seguintes fórmulas.

• Seja minHeap[] um array inteiro com raiz no índice “ i = 0; ”.
• minHeap[(i - 1) / 2] retorna o nó pai.
• minHeap[(i * 2) + 2] retorna o nó filho correto.
• minHeap[(i * 2) + 1] retorna o nó filho esquerdo.

Considerando a Figura # 2 fornecida acima, o valor da raiz (pai) = 3, o nó filho esquerdo é 13 e o nó filho direito = 7.

Implementação de Min Heap em Java - Usando Arrays

Vejamos a implementação básica de Heaps usando array, com index como a posição atual do elemento a ser adicionado e size como o tamanho total do array.

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

Saída

filas prioritárias

Uma fila de prioridade é um tipo especial de fila em que cada elemento está associado a uma prioridade e é colocado de acordo com sua prioridade. Para facilitar a implementação do min heap, usamos a classe PriorityQueue java.util.PriorityQueue fornecida pelo Java. Se os elementos fornecidos devem ser classificados/colocados em uma prioridade, então uma fila de prioridade é usada. Uma fila prioritária é diferente de uma fila simples porque as filas padrão seguem o algoritmo First-In-First-Out ( FIFO ), mas às vezes os elementos da fila precisam ser processados ​​de acordo com a prioridade, é por isso que a fila prioritária é projetada. Quando você adiciona elementos a uma fila de prioridade, um heap mínimo é criado por padrão.

Operações Comuns

Antes de prosseguirmos para a implementação, aqui estão algumas operações comuns em java.util.PriorityQueue que você precisa conhecer.

• add(int element) insere o elemento especificado em uma fila de prioridade.
• remove(int element) remove uma única instância do elemento especificado desta fila, se estiver presente.
• peek() recupera, mas não remove, o cabeçalho desta fila, ou retorna null se a fila estiver vazia.
• poll() recupera e remove o início desta fila ou retorna null se esta fila estiver vazia.
• contains() retorna “true” se esta fila contiver o elemento especificado.
• size() retorna o número de elementos nesta fila/minheap de prioridade.

Implementação de Min Heap em Java usando Priority Queues

Veja como você pode implementar um heap mínimo usando a classe de fila de prioridade 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);
	}
}

Saída

Conclusão

Heaps mínimos são amplamente usados ​​para recuperar o menor elemento em um conjunto de elementos em tempo constante. Existem muitas outras aplicações dessa estrutura de dados, mas você pode escolher qualquer método para implementá-la. Escusado será dizer que você tem que praticar com paciência para ficar bom nisso. Então, vamos colocar nossos músculos em movimento e começar a trabalhar!