what is heap data structure java
Este tutorial explica o que é Java Heap Data Structure e conceitos relacionados, como Min Heap, Max Heap, Heap Sort, Stack vs Heap com exemplos:
Um heap é uma estrutura de dados especial em Java. Um heap é uma estrutura de dados baseada em árvore e pode ser classificado como uma árvore binária completa. Todos os nós do heap são organizados em uma ordem específica.
=> Visite aqui para ver a série de treinamento Java para todos
O que você aprenderá:
- Estrutura de dados heap em Java
- Stack Vs Heap em Java
- Conclusão
Estrutura de dados heap em Java
Na estrutura de dados do heap, o nó raiz é comparado com seus filhos e organizado de acordo com a ordem. Portanto, se a é um nó raiz eb é seu filho, a propriedade, chave (a)> = chave (b) irá gerar um heap máximo.
A relação acima entre a raiz e o nó filho é chamada de “Heap Property”.
Dependendo da ordem dos nós pai-filho, o heap é geralmente de dois tipos:
# 1) Max-Heap :Em um Max-Heap, a chave do nó raiz é a maior de todas as chaves no heap. Deve-se garantir que a mesma propriedade seja verdadeira para todas as subárvores no heap recursivamente.
O diagrama abaixo mostra um Sample Max Heap. Observe que o nó raiz é maior que seus filhos.
# 2) Min-Heap :No caso de um Min-Heap, a chave do nó raiz é a menor ou mínima entre todas as outras chaves presentes no heap. Como no heap máximo, essa propriedade deve ser recursivamente verdadeira em todas as outras subárvores no heap.
Um exemplo, de uma árvore Min-heap, é mostrado abaixo. Como podemos ver, a chave raiz é a menor de todas as outras chaves no heap.
Uma estrutura de dados heap pode ser usada nas seguintes áreas:
- Heaps são usados principalmente para implementar Filas de Prioridade.
- Especialmente o min-heap pode ser usado para determinar os caminhos mais curtos entre os vértices em um gráfico.
Como já mencionado, a estrutura de dados de heap é uma árvore binária completa que satisfaz a propriedade de heap para root e filhos. Este heap também é chamado de heap binário .
Pilha Binária
Um heap binário cumpre as propriedades abaixo:
- Um heap binário é uma árvore binária completa. Em uma árvore binária completa, todos os níveis, exceto o último nível, são completamente preenchidos. No último nível, as teclas estão o mais à esquerda possível.
- Ele satisfaz a propriedade de heap. O heap binário pode ser máximo ou mínimo, dependendo da propriedade de heap que ele satisfaz.
Um heap binário é normalmente representado como um Array. Como é uma árvore binária completa, pode ser facilmente representada como um array. Portanto, em uma representação de array de heap binário, o elemento raiz será A (0), onde A é o array usado para representar o heap binário.
Então, em geral, para qualquer iºnó na representação da matriz de heap binário, A (i), podemos representar os índices de outros nós como mostrado abaixo.
| A ((i-1) / 2) | Representa o nó pai |
|---|---|
| O acesso é mais rápido. | Mais lento que a pilha. |
| A ((2 * i) +1) | Representa o nó filho esquerdo |
| A ((2 * i) +2) | Representa o nó filho certo |
Considere o seguinte heap binário:
A representação da matriz do heap binário mínimo acima é a seguinte:
Conforme mostrado acima, o heap é percorrido de acordo com o ordem nivelada ou seja, os elementos são percorridos da esquerda para a direita em cada nível. Quando os elementos de um nível se esgotam, passamos para o próximo.
A seguir, implementaremos o heap binário em Java.
O programa a seguir demonstra o heap binário em Java.
import java.util.*; class BinaryHeap { private static final int d= 2; private int() heap; private int heapSize; //BinaryHeap constructor with default size public BinaryHeap(int capacity){ heapSize = 0; heap = new int( capacity+1); Arrays.fill(heap, -1); } //is heap empty? public boolean isEmpty(){ return heapSize==0; } //is heap full? public boolean isFull(){ return heapSize == heap.length; } //return parent private int parent(int i){ return (i-1)/d; } //return kth child private int kthChild(int i,int k){ return d*i +k; } //insert new element into the heap public void insert(int x){ if(isFull()) throw new NoSuchElementException('Heap is full, No space to insert new element'); heap(heapSize++) = x; heapifyUp(heapSize-1); } //delete an element from the heap at given position public int delete(int x){ if(isEmpty()) throw new NoSuchElementException('Heap is empty, No element to delete'); int key = heap(x); heap(x) = heap(heapSize -1); heapSize--; heapifyDown(x); return key; } //maintain heap property during insertion 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; } //maintain heap property during deletion private void heapifyDown(int i){ int child; int temp = heap(i); while(kthChild(i, 1) heap(rightChild)?leftChild:rightChild; } //print the heap public void printHeap() { System.out.print('nHeap = '); for (int i = 0; i Resultado:
nHeap = 7 4 6 1 3 2 5
Min Heap em Java
Um min-heap em Java é uma árvore binária completa. No heap mínimo, o nó raiz é menor do que todos os outros nós do heap. Em geral, o valor da chave de cada nó interno é menor ou igual a seus nós filhos.
No que diz respeito à representação de array de min-heap, se um nó é armazenado na posição 'i', então seu nó filho esquerdo é armazenado na posição 2i + 1 e, em seguida, o nó filho direito está na posição 2i + 2. A posição (i-1) / 2 retorna seu nó pai.
A seguir estão listadas as várias operações suportadas pelo min-heap.
# 1) Insira (): Inicialmente, uma nova chave é adicionada ao final da árvore. Se a chave for maior do que seu nó pai, a propriedade de heap será mantida. Caso contrário, precisamos percorrer a chave para cima para cumprir a propriedade heap. A operação de inserção no heap mínimo leva tempo O (log n).
# 2) extractMin (): Esta operação remove o elemento mínimo do heap. Observe que a propriedade heap deve ser mantida após a remoção do elemento raiz (elemento min) do heap. Toda a operação leva O (Logn).
# 3) getMin (): getMin () retorna a raiz do heap, que também é o elemento mínimo. Esta operação é feita em tempo O (1).
A seguir, é fornecido um exemplo de árvore para um heap mínimo.
O diagrama acima mostra uma árvore de heap mínimo. Vemos que a raiz da árvore é o elemento mínimo da árvore. Como a raiz está no local 0, seu filho esquerdo é colocado em 2 * 0 + 1 = 1 e o filho direito em 2 * 0 + 2 = 2.
Algoritmo de pilha mínima
A seguir está o algoritmo para a construção de um heap mínimo.
procedure build_minheap Array Arr: of size N => array of elements { repeat for (i = N/2 ; i >= 1 ; i--) call procedure min_heapify (A, i); } procedure min_heapify (var A( ) , var i, var N) { var left = 2*i; var right = 2*i+1; var smallest; if(left <= N and A(left) < A( i ) ) smallest = left; else smallest = i; if(right <= N and A(right) < A(smallest) ) smallest = right; if(smallest != i) { swap A( i ) and A( smallest )); call min_heapify (A, smallest,N); } }Implementação de heap mínimo em Java
Podemos implementar o min-heap usando array ou filas de prioridade. A implementação de min-heap usando filas de prioridade é a implementação padrão, pois uma fila de prioridade é implementada como min-heap.
O programa Java a seguir implementa o min-heap usando Arrays. Aqui, usamos a representação de array para heap e, em seguida, aplicamos a função heapify para manter a propriedade heap de cada elemento adicionado ao heap. Finalmente, exibimos o heap.
class Min_Heap { private int() HeapArray; private int size; private int maxsize; private static final int FRONT = 1; //constructor to initialize the HeapArray public Min_Heap(int maxsize) { this.maxsize = maxsize; this.size = 0; HeapArray = new int(this.maxsize + 1); HeapArray(0) = Integer.MIN_VALUE; } // returns parent position for the node private int parent(int pos) { return pos / 2; } // returns the position of left child private int leftChild(int pos) { return (2 * pos); } // returns the position of right child private int rightChild(int pos) { return (2 * pos) + 1; } // checks if the node is a leaf node private boolean isLeaf(int pos) { if (pos >= (size / 2) && pos HeapArray(leftChild(pos)) || HeapArray(pos) > HeapArray(rightChild(pos))) { // swap with left child and then heapify the left child if (HeapArray(leftChild(pos)) = maxsize) { return; } HeapArray(++size) = element; int current = size; while (HeapArray(current) = 1; pos--) { minHeapify(pos); } } // remove and return the heap elment public int remove() { int popped = HeapArray(FRONT); HeapArray(FRONT) = HeapArray(size--); minHeapify(FRONT); return popped; } } class Main{ public static void main(String() arg) { //construct a min heap from given data System.out.println('The Min Heap is '); Min_Heap minHeap = new Min_Heap(7); minHeap.insert(12); minHeap.insert(15); minHeap.insert(30); minHeap.insert(40); minHeap.insert(50); minHeap.insert(90); minHeap.insert(45); minHeap.minHeap(); //display the min heap contents minHeap.display(); //display root node of the min heap System.out.println('The Min val(root node):' + minHeap.remove()); } } Resultado:
Pilha máxima em Java
Um heap máximo também é uma árvore binária completa. Em um heap máximo, o nó raiz é maior ou igual aos nós filhos. Em geral, o valor de qualquer nó interno em um heap máximo é maior ou igual a seus nós filhos.
Enquanto o heap máximo é mapeado para uma matriz, se qualquer nó for armazenado na posição 'i', então seu filho esquerdo é armazenado em 2i +1 e o filho direito é armazenado em 2i + 2.
O heap máximo típico será semelhante ao mostrado abaixo:
No diagrama acima, vemos que o nó raiz é o maior no heap e seus nós filhos têm valores menores que o nó raiz.
Semelhante ao heap mínimo, o heap máximo também pode ser representado como uma matriz.
Portanto, se A é uma matriz que representa o heap máximo, A (0) é o nó raiz. Da mesma forma, se A (i) for qualquer nó no heap máximo, os seguintes são os outros nós adjacentes que podem ser representados usando uma matriz.
- A ((i-1) / 2) representa o nó pai de A (i).
- A ((2i +1)) representa o nó filho esquerdo de A (i).
- A (2i + 2) retorna o nó filho direito de A (i).
As operações que podem ser realizadas no Max Heap são fornecidas a seguir.
# 1) Insira: A operação de inserção insere um novo valor na árvore de heap máximo. Ele é inserido no final da árvore. Se a nova chave (valor) for menor do que seu nó pai, a propriedade de heap será mantida. Caso contrário, a árvore precisa ser heapificada para manter a propriedade de heap.
sites para assistir anime em inglês dublado
A complexidade de tempo da operação de inserção é O (log n).
# 2) ExtractMax: A operação ExtractMax remove o elemento máximo (raiz) do heap máximo. A operação também monta o heap máximo para manter a propriedade de heap. A complexidade de tempo dessa operação é O (log n).
# 3) getMax: A operação getMax retorna o nó raiz do heap máximo com a complexidade de tempo de O (1).
O programa Java abaixo implementa o heap máximo. Usamos ArrayList aqui para representar os elementos de heap máximo.
import java.util.ArrayList; class Heap { void heapify(ArrayList hT, int i) { int size = hT.size(); int largest = i; int l = 2 * i + 1; int r = 2 * i + 2; if (l hT.get(largest)) largest = l; if (r hT.get(largest)) largest = r; if (largest != i) { int temp = hT.get(largest); hT.set(largest, hT.get(i)); hT.set(i, temp); heapify(hT, largest); } } void insert(ArrayList hT, int newNum) { int size = hT.size(); if (size == 0) { hT.add(newNum); } else { hT.add(newNum); for (int i = size / 2 - 1; i >= 0; i--) { heapify(hT, i); } } } void deleteNode(ArrayList hT, int num) { int size = hT.size(); int i; for (i = 0; i = 0; j--) { heapify(hT, j); } } void printArray(ArrayList array, int size) { for (Integer i : array) { System.out.print(i + ' '); } System.out.println(); } } class Main{ public static void main(String args()) { ArrayList array = new ArrayList(); int size = array.size(); Heap h = new Heap(); h.insert(array, 3); h.insert(array, 4); h.insert(array, 9); h.insert(array, 5); h.insert(array, 2); System.out.println('Max-Heap array: '); h.printArray(array, size); h.deleteNode(array, 4); System.out.println('After deleting an element: '); h.printArray(array, size); } } Resultado:
Pilha mínima da fila prioritária em Java
A estrutura de dados da fila de prioridade em Java pode ser usada diretamente para representar o min-heap. Por padrão, a fila de prioridade implementa min-heap.
O programa a seguir demonstra o min-heap em Java usando a Priority Queue.
import java.util.*; class Main { public static void main(String args()) { // Create priority queue object PriorityQueue pQueue_heap = new PriorityQueue(); // Add elements to the pQueue_heap using add() pQueue_heap.add(100); pQueue_heap.add(30); pQueue_heap.add(20); pQueue_heap.add(40); // Print the head (root node of min heap) using peek method System.out.println('Head (root node of min heap):' + pQueue_heap.peek()); // Print min heap represented using PriorityQueue System.out.println('
Min heap as a PriorityQueue:'); Iterator iter = pQueue_heap.iterator(); while (iter.hasNext()) System.out.print(iter.next() + ' '); // remove head (root of min heap) using poll method pQueue_heap.poll(); System.out.println('
Min heap after removing root node:'); //print the min heap again Iterator iter2 = pQueue_heap.iterator(); while (iter2.hasNext()) System.out.print(iter2.next() + ' '); } } Resultado:
Pilha máxima da fila prioritária em Java
Para representar o heap máximo em Java usando a fila Priority, temos que usar Collections.reverseOrder para reverter o heap mínimo. A fila de prioridade representa diretamente um min-heap em Java.
Implementamos o Heap máximo usando uma fila de prioridade no programa abaixo.
import java.util.*; class Main { public static void main(String args()) { // Create empty priority queue //with Collections.reverseOrder to represent max heap PriorityQueue pQueue_heap = new PriorityQueue(Collections.reverseOrder()); // Add items to the pQueue using add() pQueue_heap.add(10); pQueue_heap.add(90); pQueue_heap.add(20); pQueue_heap.add(40); // Printing all elements of max heap System.out.println('The max heap represented as PriorityQueue:'); Iterator iter = pQueue_heap.iterator(); while (iter.hasNext()) System.out.print(iter.next() + ' '); // Print the highest priority element (root of max heap) System.out.println('
Head value (root node of max heap):' + pQueue_heap.peek()); // remove head (root node of max heap) with poll method pQueue_heap.poll(); //print the max heap again System.out.println('
Max heap after removing root: '); Iterator iter2 = pQueue_heap.iterator(); while (iter2.hasNext()) System.out.print(iter2.next() + ' '); } } Resultado:
Classificação de heap em Java
A classificação por heap é uma técnica de classificação por comparação semelhante à classificação por seleção, na qual selecionamos um elemento máximo no array para cada iteração. A classificação de heap usa a estrutura de dados de heap e classifica os elementos criando o heap mínimo ou máximo dos elementos da matriz a serem classificados.
Já discutimos que no heap mínimo e máximo, o nó raiz contém o elemento mínimo e máximo, respectivamente, do array. Na classificação de heap, o elemento raiz do heap (mínimo ou máximo) é removido e movido para a matriz classificada. O heap restante é então heapificado para manter a propriedade do heap.
Portanto, temos que executar duas etapas recursivamente para classificar o array fornecido usando a classificação por heap.
- Construa um heap a partir da matriz fornecida.
- Remova repetidamente o elemento raiz do heap e mova-o para a matriz classificada. Heapify o heap restante.
A complexidade de tempo da classificação Heap é O (n log n) em todos os casos. A complexidade do espaço é O (1).
Algoritmo de classificação de heap em Java
A seguir, são fornecidos os algoritmos de classificação de heap para classificar a matriz fornecida em ordem crescente e decrescente.
# 1) Algoritmo de classificação de heap para classificar em ordem crescente:
- Crie um heap máximo para a matriz fornecida a ser classificada.
- Exclua a raiz (valor máximo na matriz de entrada) e mova-a para a matriz classificada. Coloque o último elemento da matriz na raiz.
- Heapify a nova raiz do heap.
- Repita as etapas 1 e 2 até que toda a matriz seja classificada.
# 2) Algoritmo de classificação de heap para classificar em ordem decrescente:
- Construa um Heap mínimo para a matriz fornecida.
- Remova a raiz (valor mínimo no array) e troque-o pelo último elemento do array.
- Heapify a nova raiz do heap.
- Repita as etapas 1 e 2 até que toda a matriz seja classificada.
Implementação de classificação de heap em Java
O programa Java abaixo usa classificação de heap para classificar uma matriz em ordem crescente. Para isso, primeiro construímos um heap máximo e, em seguida, trocamos e montamos recursivamente o elemento raiz conforme especificado no algoritmo acima.
import java.util.*; class HeapSort{ public void heap_sort(int heap_Array()) { int heap_len = heap_Array.length; // construct max heap for (int i = heap_len / 2 - 1; i >= 0; i--) { heapify(heap_Array, heap_len, i); } // Heap sort for (int i = heap_len - 1; i >= 0; i--) { int temp = heap_Array(0); heap_Array(0) = heap_Array(i); heap_Array(i) = temp; // Heapify root element heapify(heap_Array, i, 0); } } void heapify(int heap_Array(), int n, int i) { // find largest value int largest = i; int left = 2 * i + 1; int right = 2 * i + 2; if (left heap_Array(largest)) largest = left; if (right heap_Array(largest)) largest = right; // recursively heapify and swap if root is not the largest if (largest != i) { int swap = heap_Array(i); heap_Array(i) = heap_Array(largest); heap_Array(largest) = swap; heapify(heap_Array, n, largest); } } } class Main{ public static void main(String args()) { //define input array and print it int heap_Array() = {6,2,9,4,10,15,1,13}; System.out.println('Input Array:' + Arrays.toString(heap_Array)); //call HeapSort method for given array HeapSort hs = new HeapSort(); hs.heap_sort(heap_Array); //print the sorted array System.out.println('Sorted Array:' + Arrays.toString(heap_Array)); } } Resultado:
A complexidade geral de tempo da técnica de classificação de heap é O (nlogn). A complexidade de tempo da técnica heapify é O (logn). Enquanto a complexidade de tempo de construção do heap é O (n).
Stack Vs Heap em Java
Vamos agora tabular algumas das diferenças entre uma estrutura de dados Stack e heap.
Pilha Heap Uma pilha é uma estrutura de dados linear. Um heap é uma estrutura de dados hierárquica. Segue a ordem LIFO (último a entrar, primeiro a sair). Traversal está em ordem nivelada. Principalmente usado para alocação de memória estática. Usado para alocação de memória dinâmica. A memória é alocada de forma contígua. A memória é alocada em locais aleatórios. O tamanho da pilha é limitado de acordo com o sistema operacional. Nenhum limite de tamanho de heap imposto pelo sistema operacional. Stack tem acesso apenas a variáveis locais. O heap possui variáveis globais alocadas a ele. A alocação / desalocação de memória é automática. A alocação / desalocação precisa ser feita manualmente pelo programador. A pilha pode ser implementada usando Arrays, Linked List, ArrayList, etc. ou qualquer outra estrutura de dados linear. Heap é implementado usando Arrays ou árvores. Custo de manutenção, se menor. Mais caro de manter. Pode resultar em falta de memória, pois a memória é limitada. Não há falta de memória, mas pode sofrer fragmentação da memória.
perguntas frequentes
P # 1) A pilha é mais rápida do que a pilha?
Responda: Uma pilha é mais rápida do que a pilha, pois o acesso é linear na pilha em comparação com a pilha.
P # 2) Para que é usado um Heap?
Responda: Heap é usado principalmente em algoritmos que encontram o caminho mínimo ou mais curto entre dois pontos como o algoritmo de Dijkstra, para classificar usando classificação de heap, para implementações de fila de prioridade (min-heap), etc.
P # 3) O que é um Heap? Quais são seus tipos?
Responda: Um heap é uma estrutura de dados hierárquica baseada em árvore. Um heap é uma árvore binária completa. Pilhas são de dois tipos, ou seja, pilha máxima em que o nó raiz é o maior entre todos os nós; Pilha mínima em que o nó raiz é o menor ou mínimo entre todas as chaves.
P # 4) Quais são as vantagens do Heap em relação a uma pilha?
Responda: A principal vantagem do heap sobre a pilha está no heap, a memória é alocada dinamicamente e, portanto, não há limite de quanta memória pode ser usada. Em segundo lugar, apenas variáveis locais podem ser alocadas na pilha, enquanto também podemos alocar variáveis globais na pilha.
P # 5) O Heap pode ter duplicatas?
Responda: Sim, não há restrições em ter nós com chaves duplicadas no heap, pois o heap é uma árvore binária completa e não satisfaz as propriedades da árvore de pesquisa binária.
Conclusão
Neste tutorial, discutimos os tipos de heap e classificação de heap usando tipos de heap. Também vimos a implementação detalhada de seus tipos em Java.
=> Confira o guia de treinamento Java perfeito aqui.
Leitura recomendada
- Tutorial do Java Graph - Como implementar a estrutura de dados do gráfico
- Introdução às estruturas de dados em C ++
- Classificação de heap em C ++ com exemplos
- Árvore AVL e estrutura de dados heap em C ++
- Estrutura de dados de árvore binária em C ++
- Estrutura de dados da fila em C ++ com ilustração
- Estrutura de dados de lista vinculada circular em C ++ com ilustração
- Java Basics: Java Syntax, Java Class e Core Java Concepts
