Entenda como implementar um heap binário em Java



Este artigo fornecerá um conhecimento detalhado e abrangente de como impulsionar um heap binário em java com exemplos.

Este artigo lhe dará uma visão geral completa do funcionamento da classificação de heap e, posteriormente, aprenderemos a implementar um heap binário em Java.

Aqui está a agenda para este artigo:





  1. O que é tipo de heap?
  2. Pilha máxima
  3. Min Heap
  4. Implementação de heap em Java
    • Diagrama
    • Código

Vamos começar!

O que é tipo de heap?

Heap é basicamente uma estrutura de dados baseada em árvore. Possui nós. O nó é composto por certos elementos. Cada nó contém um elemento.



Os nós podem ter filhos. Se não houver filhos, é chamado de Folha.

Existem duas regras a serem seguidas:

  • O valor de cada nó deve ser menor ou igual a todos os valores armazenados em seus filhos.
  • Tem a menor altura possível.

Heaps são extremamente eficientes na extração domenor ou maior elemento.



Vamos passar para o min heap agora!

Min Heap

O heap mínimo é uma árvore binária completa em que o valor do elemento raiz é menor ou igual a qualquer um dos elementos filho.

Representação de pilha mínima

Arr [(i-1) / 2]: isso retornará o nó pai.

classe vs interface em java

Arr [(2 * i) + 1]: isso retornará o nó filho esquerdo.

Arr [(2 * i) + 2]: isso retornará o nó filho correto.

Existem certos métodos de Min Heap:

  • inserir(): Uma nova chave no final da árvore é adicionada. No caso da nova chave ser maior que a do pai, não há necessidade de fazer nada, senão, temos que atravessar para configurar a propriedade heap.
  • getMin (): este método ajuda a retornar o elemento raiz.
  • extractMin (): este método retorna o mínimoelemento.

Passando para a pilha de Max agora.

Pilha máxima

O heap máximo é uma árvore binária completa na qual o valor do elemento raiz é maior ou igual a qualquer um dos elementos filho.

A pilha máxima também consiste em vários métodos!

  • Inserir (): ele irá inserir um elemento na pilha.
  • Excluir() : ele irá deletar um elemento da pilha.
  • FindMax (): ele encontrará o elemento máximo do heap.
  • printHeap (): Irá imprimir o conteúdo da pilha

Agora, deixe-me mostrar a implementação de heap por meio de um diagrama e, posteriormente, um Javacódigo.

Implementação de heap em Java

Diagrama:

Heap

O diagrama acima mostra o heap binário em Java. Como você aprendeu que existem duas pilhas: Pilha mínima e pilha máxima, aqui está um diagrama:

java criar matriz de objetos

Agora, passando para o nosso próximo segmento, veremos como implementar um heap binário em Java.

Código:

public class BinaryHeap {private static final int d = 2 private int [] heap private int heapSize / ** * Isso inicializará nosso heap com o tamanho padrão. * / public BinaryHeap (int capacity) {heapSize = 0 heap = new int [capacity + 1] Arrays.fill (heap, -1)} / ** * Isso verificará se o heap está vazio ou não * Complexidade: O ( 1) * / public boolean isEmpty () {return heapSize == 0} / ** * Isso verificará se o heap está cheio ou não * Complexidade: O (1) * / public boolean isFull () {return heapSize == heap .length} private int pai (int i) {return (i-1) / d} private int kthChild (int i, int k) {return d * i + k} / ** * Isto irá inserir um novo elemento no heap * Complexidade: O (log N) * Como pior cenário, precisamos percorrer até a raiz * / public void insert (int x) {if (isFull ()) throw new NoSuchElementException ('Heap is full, No space to insert novo elemento ') heap [heapSize ++] = x heapifyUp (heapSize-1)} / ** * Isso excluirá o elemento no índice x * Complexidade: O (log N) * * / public int delete (int x) {if (isEmpty ()) lançar novo NoSuchElementException ('Heap está vazio, Nenhum elemento para deletar') chave int = heap [x] heap [x] = heap [heapSize -1] heapSize-- heapifyDown (x) retu rn key} / ** * Este método usado para manter a propriedade heap ao inserir um elemento. * * / private void heapifyUp (int i) {int temp = heap [i] while (i> 0 && temp> heap [parent (i)]) {heap [i] = heap [parent (i)] i = parent (i)} heap [i] = temp} / ** * Este método usado para manter a propriedade heap ao excluir um elemento. * * / private void heapifyDown (int i) {int child int temp = heap [i] while (kthChild (i, 1)heap [rightChild]? leftChild: rightChild} / ** * Este método usado para imprimir todos os elementos do heap * * / public void printHeap () {System.out.print ('nHeap =') for (int i = 0 i

Com isso, chegamos ao final deste artigo sobre Binary Heap em Java. Confira o pela Edureka, uma empresa de aprendizagem online confiável com uma rede de mais de 250.000 alunos satisfeitos espalhados por todo o mundo. O curso de certificação e treinamento Java J2EE e SOA da Edureka é projetado para estudantes e profissionais que desejam ser um desenvolvedor Java. O curso foi elaborado para dar a você uma vantagem inicial na programação Java e treiná-lo para os conceitos básicos e avançados de Java, juntamente com várias estruturas Java como Hibernate e Spring.

Tem alguma questão para nós? Mencione isso na seção de comentários deste blog “Java ArrayList” e entraremos em contato com você o mais breve possível.