Introdução ao Heap Sort In Java
O Heapsort em Java é uma técnica de classificação baseada em comparação, na qual a estrutura de dados Binary Heap é usada. Essa classificação é quase a mesma da classificação de seleção, onde o maior elemento será selecionado e os lugares serão colocados no final, e o processo será repetido para todos os elementos. Para entender a Classificação de pilha, vamos ver o que Classificação de pilha binária em Java.
- Estrutura de dados baseada em árvore.
- Árvore binária completa.
- Pode ter até dois filhos.
- O valor no nó raiz pode ser maior (heap máximo) ou menor (heap mínimo)
Como o Heap Sort funciona em Java?
Antes de passar para o algoritmo, vamos ver o que é Heapify.
Heapify
Depois que um heap é criado com os dados de entrada, a propriedade heap pode não ser satisfeita. Para alcançá-lo, uma função chamada heapify será usada para ajustar os nós do heap. Se quisermos criar heap máximo, o elemento atual será comparado com seus filhos e se o valor de filhos for maior que o elemento atual, a troca será feita com o maior elemento em um filho esquerdo ou direito. Da mesma forma, se for necessário criar um min-heap, a troca será feita com o menor elemento no filho esquerdo ou direito. Por exemplo, a seguir é nossa matriz de entrada,
Podemos considerar isso como uma árvore em vez de uma matriz. O primeiro elemento será raiz, o segundo será o filho esquerdo da raiz, o terceiro elemento será o filho direito da raiz e assim por diante.
Para transformar o heap em uma árvore, atravesse a árvore em uma direção de baixo para cima. Como os nós das folhas não têm filhos, vejamos o próximo nível. ou seja, é 5 e 7.
Podemos começar às 5, à esquerda. Aqui, 5 tem dois filhos: 9 e 4, onde 9 é maior que o nó pai 5. Para aumentar os pais, trocaremos 5 e 9. Após a troca, a árvore será mostrada abaixo.
Vamos para o próximo elemento 7, onde 8 e 2 são os filhos. Semelhante aos elementos 9 e 4, 7 e 8 serão trocados como na árvore abaixo.
Finalmente, 3 tem dois filhos - 9 e 8, onde 9 é maior entre os filhos e a raiz. Portanto, a troca de 3 e 9 será feita para aumentar a raiz. Repita o processo até que um heap válido seja formado, como mostrado abaixo.
Algoritmo para Heap Ordenar em ordem crescente
- Crie um heap máximo com os dados de entrada
- Substitua o último elemento pelo maior elemento na pilha
- Heapify the Tree
- Repita o processo até que a matriz seja classificada
Algoritmo para Heap Ordenar em ordem decrescente
- Crie uma pilha mínima com os dados de entrada
- Substitua o último elemento pelo menor elemento na pilha
- Heapify the Tree
- Repita o processo até que a matriz seja classificada
Agora, vamos tentar classificar o Heap obtido acima na ordem crescente usando o algoritmo fornecido. Primeiro, remova o elemento maior. ou seja, root e substitua-o pelo último elemento.
Agora, empilhe a árvore formada e insira o elemento removido no último da matriz, como mostrado abaixo
Mais uma vez, remova o elemento raiz, substitua-o pelo último elemento e Heapify.
Insira o elemento removido na posição vaga. Agora você pode ver que o final da matriz está sendo classificado.
Agora, remova o elemento 7 e substitua-o por 2.
Heapify a árvore, como mostrado abaixo.
Repita o processo até que a matriz seja classificada. Removendo o elemento 5.
Heapifying a árvore.
Removendo o elemento 4.
Heapfying novamente.
Por fim, uma matriz classificada como essa será formada.
Exemplos para implementar a classificação de pilha em Java
Agora, vamos ver o código fonte do Heap Sort em Java
//Java program to sort the elements using Heap sort
import java.util.Arrays;
public class HeapSort (
public void sort(int array()) (
int size = array.length; //Assigning the length of array in a variable
// Create heap
for (int i = size / 2 - 1; i >= 0; i--)
heapify(array, size, i);
//Find the maximum element and replace it with the last element in the array
for (int i=size-1; i>=0; i--) (
int x = array(0);//largest element(It is available in the root)
array(0) = array(i);
array(i) = x;
// Recursively call heapify until a heap is formed
heapify(array, i, 0);
)
)
// Heapify function
void heapify(int array(), int SizeofHeap, int i) (
int largestelement = i; // Set largest element as root
int leftChild = 2*i + 1; // index of left child = 2*i + 1
int rightChild = 2*i + 2; //index of right child = 2*i + 2
// left child is greater than root
if (leftChild array(largestelement))
largestelement = leftChild ;
//right child is greater than largest
if (rightChild array(largestelement))
largestelement = rightChild ;
// If largestelement is not root
if (largestelement != i) (
int temp = array(i);
array(i) = array(largestelement);
array(largestelement) = temp;
// Recursive call to heapify the sub-tree
heapify(array, SizeofHeap, largestelement);
)
)
public static void main(String args()) (
int array() = (3, 5, 7, 9, 4, 8, 2);
System. out .println("Input array is: " + Arrays. toString (array));
HeapSort obj = new HeapSort();
obj.sort(array);
System. out .println("Sorted array is : " + Arrays. toString (array));
)
)
Resultado
Conclusão
A classificação de heap é uma técnica de classificação que depende da estrutura de dados de heap binária. É quase semelhante à classificação de seleção e não usa matrizes separadas para classificação e heap.
Artigo recomendado
Este foi um guia para o Heap Sort em Java. Aqui discutimos o trabalho, Classificando o algoritmo com ordem crescente e decrescente e exemplos com código de exemplo. Você também pode consultar nossos outros artigos sugeridos para saber mais -
- Funções matemáticas de JavaScript
- Layout em Java
- Compiladores Java
- Guia para mesclar classificação em Java
- Guia de Heap Sort em C
- Exemplos de classificação de heap em C ++