heap sort c with examples
Uma introdução à classificação de heap com exemplos.
Heapsort é uma das técnicas de classificação mais eficientes. Essa técnica cria um heap a partir do array não classificado fornecido e, em seguida, usa o heap novamente para classificar o array.
Heapsort é uma técnica de classificação baseada em comparação e usa heap binário.
=> Leia a série de treinamento Easy C ++.
como começar a carreira em teste de software
O que você aprenderá:
- O que é um heap binário?
- Algoritmo Geral
- Ilustração
- Exemplo C ++
- Exemplo de Java
- Conclusão
- Leitura recomendada
O que é um heap binário?
Um heap binário é representado usando uma árvore binária completa. Uma árvore binária completa é uma árvore binária na qual todos os nós em cada nível são completamente preenchidos, exceto os nós folha e os nós estão na parte esquerda.
Um heap binário ou simplesmente um heap é uma árvore binária completa onde os itens ou nós são armazenados de forma que o nó raiz seja maior do que seus dois nós filhos. Isso também é chamado de heap máximo.
Os itens no heap binário também podem ser armazenados como min-heap, em que o nó raiz é menor do que seus dois nós filhos. Podemos representar um heap como uma árvore binária ou um array.
Ao representar um heap como uma matriz, supondo que o índice comece em 0, o elemento raiz é armazenado em 0. Em geral, se um nó pai está na posição I, o nó filho esquerdo está na posição (2 * I + 1) e o nó direito está em (2 * I +2).
Algoritmo Geral
A seguir, é fornecido o algoritmo geral para a técnica de classificação de heap.
- Crie um heap máximo a partir dos dados fornecidos, de forma que a raiz seja o elemento mais alto do heap.
- Remova a raiz, ou seja, o elemento mais alto do heap e substitua ou troque pelo último elemento do heap.
- Em seguida, ajuste o heap máximo, de modo a não violar as propriedades do heap máximo (heapify).
- A etapa acima reduz o tamanho do heap em 1.
- Repita as três etapas acima até que o tamanho do heap seja reduzido para 1.
Conforme mostrado no algoritmo geral para classificar o conjunto de dados fornecido em ordem crescente, primeiro construímos um heap máximo para os dados fornecidos.
Vamos dar um exemplo para construir um heap máximo com o seguinte conjunto de dados.
6, 10, 2, 4, 1
Podemos construir uma árvore para este conjunto de dados da seguinte maneira.
Na representação em árvore acima, os números entre colchetes representam as respectivas posições na matriz.
Para construir um heap máximo da representação acima, precisamos cumprir a condição de heap de que o nó pai deve ser maior do que seus nós filhos. Em outras palavras, precisamos “heapificar” a árvore para convertê-la em heap máximo.
Após a heapificação da árvore acima, obteremos o heap máximo conforme mostrado abaixo.
Conforme mostrado acima, temos esse heap máximo gerado a partir de uma matriz.
A seguir, apresentamos uma ilustração de um tipo de heap. Tendo visto a construção do heap máximo, ignoraremos as etapas detalhadas para construir um heap máximo e mostraremos diretamente o heap máximo em cada etapa.
Ilustração
Considere a seguinte matriz de elementos. Precisamos classificar esse array usando a técnica de classificação de heap.
Vamos construir um heap máximo, conforme mostrado abaixo, para a matriz a ser classificada.
Uma vez que o heap é construído, nós o representamos em uma forma de array, conforme mostrado abaixo.
Agora comparamos o 1stnó (raiz) com o último nó e, em seguida, troque-os. Assim, como mostrado acima, trocamos 17 e 3 de modo que 17 esteja na última posição e 3 na primeira posição.
Agora, removemos o nó 17 do heap e o colocamos na matriz classificada, conforme mostrado na parte sombreada abaixo.
Agora, construímos novamente um heap para os elementos do array. Desta vez, o tamanho do heap é reduzido em 1, pois excluímos um elemento (17) do heap.
A pilha dos elementos restantes é mostrada abaixo.
Na próxima etapa, vamos repetir as mesmas etapas.
Comparamos e trocamos o elemento raiz e o último elemento no heap.
Após a troca, excluímos o elemento 12 do heap e o deslocamos para a matriz classificada.
Mais uma vez, construímos um heap máximo para os elementos restantes, conforme mostrado abaixo.
Agora trocamos a raiz e o último elemento, ou seja, 9 e 3. Após a troca, o elemento 9 é excluído do heap e colocado em uma matriz classificada.
como executar arquivos .swf
Neste ponto, temos apenas três elementos no heap, conforme mostrado abaixo.
Trocamos 6 e 3 e excluímos o elemento 6 do heap e o adicionamos ao array classificado.
Agora, construímos uma pilha dos elementos restantes e, em seguida, trocamos os dois.
Depois de trocar 4 e 3, excluímos o elemento 4 do heap e o adicionamos ao array classificado. Agora temos apenas um nó restante no heap, conforme mostrado abaixo .
Portanto, agora com apenas um nó restante, o excluímos do heap e o adicionamos ao array classificado.
Portanto, o mostrado acima é a matriz classificada que obtivemos como resultado da classificação do heap.
Na ilustração acima, classificamos a matriz em ordem crescente. Se tivermos que classificar a matriz em ordem decrescente, precisaremos seguir as mesmas etapas, mas com o heap mínimo.
O algoritmo Heapsort é idêntico à classificação de seleção, na qual selecionamos o menor elemento e o colocamos em uma matriz classificada. No entanto, a classificação de heap é mais rápida do que a classificação de seleção no que diz respeito ao desempenho. Podemos colocá-lo como heapsort é uma versão aprimorada do tipo de seleção.
A seguir, implementaremos o Heapsort em linguagem C ++ e Java.
A função mais importante em ambas as implementações é a função “heapify”. Esta função é chamada pela rotina heapsort principal para reorganizar a subárvore assim que um nó é excluído ou quando o heap máximo é construído.
Quando tivermos heapificado a árvore corretamente, só então seremos capazes de obter os elementos corretos em suas posições adequadas e, assim, o array será classificado corretamente.
Exemplo C ++
A seguir está o código C ++ para implementação de heapsort.
#include using namespace std; // function to heapify the tree void heapify(int arr[], int n, int root) { int largest = root; // root is the largest element int l = 2*root + 1; // left = 2*root + 1 int r = 2*root + 2; // right = 2*root + 2 // If left child is larger than root if (l arr[largest]) largest = l; // If right child is larger than largest so far if (r arr[largest]) largest = r; // If largest is not root if (largest != root) { //swap root and largest swap(arr[root], arr[largest]); // Recursively heapify the sub-tree heapify(arr, n, largest); } } // implementing heap sort void heapSort(int arr[], int n) { // build heap for (int i = n / 2 - 1; i >= 0; i--) heapify(arr, n, i); // extracting elements from heap one by one for (int i=n-1; i>=0; i--) { // Move current root to end swap(arr[0], arr[i]); // again call max heapify on the reduced heap heapify(arr, i, 0); } } /* print contents of array - utility function */ void displayArray(int arr[], int n) { for (int i=0; i Resultado:
Matriz de entrada
4 17 3 12 9 6
Matriz ordenada
3 4 6 9 12 17
A seguir, implementaremos o heapsort na linguagem Java
Exemplo de Java
// Java program to implement Heap Sort class HeapSort { public void heap_sort(int arr[]) { int n = arr.length; // Build heap (rearrange array) for (int i = n / 2 - 1; i >= 0; i--) heapify(arr, n, i); // One by one extract an element from heap for (int i=n-1; i>=0; i--) { // Move current root to end int temp = arr[0]; arr[0] = arr[i]; arr[i] = temp; // call max heapify on the reduced heap heapify(arr, i, 0); } } // heapify the sub-tree void heapify(int arr[], int n, int root) { int largest = root; // Initialize largest as root int l = 2*root + 1; // left = 2*root + 1 int r = 2*root + 2; // right = 2*root + 2 // If left child is larger than root if (l arr[largest]) largest = l; // If right child is larger than largest so far if (r arr[largest]) largest = r; // If largest is not root if (largest != root) { int swap = arr[root]; arr[root] = arr[largest]; arr[largest] = swap; // Recursively heapify the affected sub-tree heapify(arr, n, largest); } } //print array contents - utility function static void displayArray(int arr[]) { int n = arr.length; for (int i=0; i Resultado:
Matriz de entrada:
4 17 3 12 9 6
Matriz classificada:
3 4 6 9 12 17
Conclusão
Heapsort é uma técnica de classificação baseada em comparação que usa heap binário.
Pode ser denominado como uma melhoria em relação à classificação por seleção, uma vez que ambas as técnicas de classificação funcionam com lógica semelhante de encontrar o maior ou o menor elemento na matriz repetidamente e, em seguida, colocá-lo na matriz classificada.
A classificação de heap usa o heap máximo ou o heap mínimo para classificar a matriz. A primeira etapa na classificação do heap é construir um heap mínimo ou máximo a partir dos dados da matriz e, em seguida, excluir o elemento raiz recursivamente e heapificar o heap até que haja apenas um nó presente no heap.
Heapsort é um algoritmo eficiente e executa mais rápido do que a classificação por seleção. Ele pode ser usado para classificar um array quase ordenado ou encontrar k maiores ou menores elementos no array.
qa conduzir perguntas e respostas da entrevista
Com isso, concluímos nosso tópico sobre técnicas de classificação em C ++. De nosso próximo tutorial em diante, começaremos com as estruturas de dados uma por uma.
=> Procure toda a série de treinamento C ++ aqui.
Leitura recomendada
- Método MongoDB Sort () com exemplos
- Comando de classificação Unix com sintaxe, opções e exemplos
- Mesclar classificação em C ++ com exemplos
- Classificação Shell em C ++ com exemplos
- Classificação de inserção em C ++ com exemplos
- Classificação de seleção em C ++ com exemplos
- Classificação por bolha em C ++ com exemplos
- Classificação rápida em C ++ com exemplos