Introdução à classificação de heap em C ++
O Heapsort é uma das técnicas de classificação baseada em comparação e faz parte da classificação. Onde a classificação é definida como organizar conjuntos de dados em alguma ordem específica, usando um valor exclusivo conhecido como elemento chave na lista fornecida. O termo classificação foi introduzido quando as pessoas sabiam a importância de pesquisar qualquer elemento em um determinado conjunto de informações, caso contrário, seria muito difícil pesquisar em qualquer registro se este não estivesse ordenado e não classificado.
Existem muitas técnicas diferentes envolvidas na classificação, cada uma com sua respectiva eficiência no tempo necessário para classificar os dados e os requisitos de espaço na memória. Eles são classificação por bolha, classificação por inserção, classificação por seleção, classificação rápida, classificação por mesclagem e classificação por heap.
O que é Heap Sort?
O Heapsort é uma abordagem de classificação baseada na estrutura de dados de heap binária semelhante à classificação de seleção, onde primeiro obtemos o conjunto máximo de dados e o colocamos no final e continuamos pelo restante dos elementos.
Heapsort como o próprio nome sugere. Primeiro, ele cria o monte de elementos de dados da matriz não classificada especificada e, em seguida, verifica o item maior e o coloca no final da matriz parcialmente classificada. Ele reconstrói novamente o heap, procura o próximo maior registro e o coloca no próximo slot vazio, a partir do final do arranjo pela metade dos registros. Esse processo é repetido até que nenhum item seja deixado na pilha. Essa técnica requer duas matrizes uma para armazenar a pilha e a outra para uma matriz classificada.
Algoritmo de classificação de heap em C ++
- Primeiro, escolha root como um elemento elevado do conjunto de elementos de informações fornecido para criar um heap máximo.
- Reconstrua a pilha colocando ou trocando a raiz com o último elemento.
- O tamanho da pilha agora será reduzido em 1.
- Em seguida, criamos novamente o heap com os elementos restantes e continuamos até que o tamanho do heap seja reduzido para 1.
Exemplo de classificação de heap em C ++
Essa técnica usa heap binário que é construído usando uma árvore binária completa em que o nó raiz é maior que seus dois nós filhos.
Considere a matriz fornecida de conjuntos de dados.
Vamos de acordo com o algoritmo. Ele diz para selecionar o elemento mais alto como raiz e construir a pilha máxima.
1. Primeira Iteração
Agora a matriz terá o formato:
Agora a matriz classificada terá o formato:
O tamanho da pilha será reduzido em 1, agora 6-1 = 5.
2. Segunda Iteração
Então agora a pilha se parece com:
A matriz é da forma:
A matriz classificada será:
O tamanho do heap será reduzido em 1, agora 5-1 = 4.
3. Terceira Iteração
O novo heap se parece com:
A matriz é da forma:
A matriz classificada será:
O tamanho da pilha será reduzido em 1, agora 4-1 = 3.
4. Quarta Iteração
O novo heap se parece com:
A matriz é da forma:
A matriz classificada será:
O tamanho da pilha será reduzido em 1, agora 3-1 = 2.
5. Quinta Iteração
O novo heap se parece com:
A matriz é da forma:
A matriz classificada será:
O tamanho da pilha será reduzido em 1, agora 2-1 = 1.
6. Última Iteração
O novo heap se parece com:
A matriz possui:
4
A partir do algoritmo, executamos todas as etapas até o tamanho da pilha ser 1. Portanto, agora temos a matriz classificada:
Portanto, a matriz classificada do heap máximo está em ordem crescente. Se precisarmos que a matriz seja classificada em ordem decrescente, siga as etapas acima com um mínimo de heap.
O programa C ++ para classificação de heap é o seguinte:
#include
using namespace std;
void heapify(int arr(), int n, int i)
(
int largest = i;
int l = 2 * i + 1;
int r = 2 * i + 2;
if (l arr(largest))
largest = l;
if (r arr(largest))
largest = r;
if (largest != i) (
swap(arr(i), arr(largest));
heapify(arr, n, largest);
)
)
void heapSort(int arr(), int n)
(
for (int i = n / 2 - 1; i >= 0; i--)
heapify(arr, n, i);
for (int i = n - 1; i >= 0; i--)
(
swap(arr(0), arr(i));
heapify(arr, i, 0);
)
)
void printArray(int arr(), int n)
(
for (int i = 0; i < n; ++i)
cout << arr(i) << " ";
cout << "\n";
)
int main()
(
int arr() = ( 5, 18, 4, 13, 10, 7);
int n = sizeof(arr) / sizeof(arr(0));
heapSort(arr, n);
cout << "Sorted array is \n";
printArray(arr, n);
)
Resultado:
Conclusão
Heapsort é a técnica baseada em comparação que é o aprimoramento da classificação por seleção. A classificação de heap utiliza a seleção do elemento mais alto ou mais baixo na matriz especificada para classificar em ordem crescente ou decrescente, respectivamente, com o heap máximo ou mínimo. Realize esse processo até obtermos um tamanho do heap. Essa técnica de classificação também é usada para encontrar o maior e o menor elemento na matriz. A técnica de classificação de heap é mais eficiente e mais rápida que a técnica de classificação de seleção.
Artigos recomendados
Este é um guia para Heap Sort em C ++. Aqui discutimos o que é classificação de pilha no c ++, trabalhando com seu algoritmo e exemplo. Você também pode consultar os seguintes artigos para saber mais:
- Heap Classificar em C
- Heap Sort In Java
- Sobrecarga em C ++
- Ponteiros em C ++
- Sobrecarga em Java