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:
- O que é tipo de heap?
- Pilha máxima
- Min Heap
- 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:
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.