Neste artigo, discutiremos o algoritmo Heapsort. A classificação de heap processa os elementos criando o heap mínimo ou o heap máximo usando os elementos de uma determinada matriz. Min-heap ou max-heap representa a ordem do array em que o elemento raiz representa o elemento mínimo ou máximo do array.
A classificação de heap basicamente executa recursivamente duas operações principais -
- Construa um heap H, usando os elementos do array.
- Exclua repetidamente o elemento raiz do heap formado em 1stEstágio.
Antes de saber mais sobre a classificação de heap, vamos primeiro ver uma breve descrição de Pilha.
O que é uma pilha?
Um heap é uma árvore binária completa, e a árvore binária é uma árvore na qual o nó pode ter no máximo dois filhos. Uma árvore binária completa é uma árvore binária na qual todos os níveis, exceto o último nível, ou seja, o nó folha, devem ser completamente preenchidos e todos os nós devem ser justificados à esquerda.
O que é classificação de heap?
Heapsort é um algoritmo de classificação popular e eficiente. O conceito de classificação heap é eliminar os elementos um por um da parte heap da lista e, em seguida, inseri-los na parte classificada da lista.
Heapsort é o algoritmo de classificação local.
Neena Gupta
Agora, vamos ver o algoritmo de classificação de heap.
Algoritmo
HeapSort(arr) BuildMaxHeap(arr) for i = length(arr) to 2 swap arr[1] with arr[i] heap_size[arr] = heap_size[arr] ? 1 MaxHeapify(arr,1) End
BuildMaxHeap(arr)
BuildMaxHeap(arr) heap_size(arr) = length(arr) for i = length(arr)/2 to 1 MaxHeapify(arr,i) End
MaxHeapify(arr,i)
MaxHeapify(arr,i) L = left(i) R = right(i) if L ? heap_size[arr] and arr[L] > arr[i] largest = L else largest = i if R ? heap_size[arr] and arr[R] > arr[largest] largest = R if largest != i swap arr[i] with arr[largest] MaxHeapify(arr,largest) End
Algoritmo de classificação de heap
Agora, vamos ver o funcionamento do Algoritmo Heapsort.
Na classificação heap, basicamente, existem duas fases envolvidas na classificação dos elementos. Usando o algoritmo de classificação de heap, eles são os seguintes -
- A primeira etapa inclui a criação de um heap ajustando os elementos do array.
- Após a criação do heap, agora remova o elemento raiz do heap repetidamente, deslocando-o para o final da matriz e, em seguida, armazene a estrutura do heap com os elementos restantes.
Agora vamos ver o funcionamento do heap sort em detalhes usando um exemplo. Para entender isso mais claramente, vamos pegar um array não classificado e tentar classificá-lo usando heap sort. Isso tornará a explicação mais clara e fácil.
Primeiro, temos que construir um heap a partir do array fornecido e convertê-lo em heap máximo.
Depois de converter o heap fornecido em heap máximo, os elementos da matriz são -
Em seguida, temos que excluir o elemento raiz (89) do heap máximo. Para excluir este nó, temos que trocá-lo pelo último nó, ou seja, (onze). Depois de excluir o elemento raiz, temos que heapificá-lo novamente para convertê-lo em heap máximo.
Depois de trocar o elemento da matriz 89 com onze, e convertendo o heap em max-heap, os elementos do array são -
Na próxima etapa, novamente, temos que excluir o elemento raiz (81) do heap máximo. Para excluir este nó, temos que trocá-lo pelo último nó, ou seja, (54). Depois de excluir o elemento raiz, temos que heapificá-lo novamente para convertê-lo em heap máximo.
Depois de trocar o elemento da matriz 81 com 54 e convertendo o heap em max-heap, os elementos do array são -
Na próxima etapa, temos que excluir o elemento raiz (76) do heap máximo novamente. Para excluir este nó, temos que trocá-lo pelo último nó, ou seja, (9). Depois de excluir o elemento raiz, temos que heapificá-lo novamente para convertê-lo em heap máximo.
Depois de trocar o elemento da matriz 76 com 9 e convertendo o heap em max-heap, os elementos do array são -
Na próxima etapa, novamente temos que excluir o elemento raiz (54) do heap máximo. Para excluir este nó, temos que trocá-lo pelo último nó, ou seja, (14). Depois de excluir o elemento raiz, temos que heapificá-lo novamente para convertê-lo em heap máximo.
Depois de trocar o elemento da matriz 54 com 14 e convertendo o heap em max-heap, os elementos do array são -
Na próxima etapa, novamente temos que excluir o elemento raiz (22) do heap máximo. Para excluir este nó, temos que trocá-lo pelo último nó, ou seja, (onze). Depois de excluir o elemento raiz, temos que heapificá-lo novamente para convertê-lo em heap máximo.
Depois de trocar o elemento da matriz 22 com onze e convertendo o heap em max-heap, os elementos do array são -
Na próxima etapa, novamente temos que excluir o elemento raiz (14) do heap máximo. Para excluir este nó, temos que trocá-lo pelo último nó, ou seja, (9). Depois de excluir o elemento raiz, temos que heapificá-lo novamente para convertê-lo em heap máximo.
Depois de trocar o elemento da matriz 14 com 9 e convertendo o heap em max-heap, os elementos do array são -
Na próxima etapa, novamente temos que excluir o elemento raiz (onze) do heap máximo. Para excluir este nó, temos que trocá-lo pelo último nó, ou seja, (9). Depois de excluir o elemento raiz, temos que heapificá-lo novamente para convertê-lo em heap máximo.
Depois de trocar o elemento da matriz onze com 9, os elementos da matriz são -
Agora, o heap tem apenas um elemento restante. Depois de excluí-lo, o heap ficará vazio.
Após a conclusão da classificação, os elementos da matriz são -
np.log
Agora, o array está completamente classificado.
Complexidade de classificação de heap
Agora, vamos ver a complexidade de tempo da classificação Heap no melhor caso, no caso médio e no pior caso. Veremos também a complexidade espacial do Heapsort.
1. Complexidade de tempo
| Caso | Complexidade de tempo |
|---|---|
| Melhor caso | O (n registro) |
| Caso médio | Sobre (n log n) |
| Pior caso | Sobre (n log n) |
A complexidade de tempo da classificação de heap é O (n registro) em todos os três casos (melhor caso, caso médio e pior caso). A altura de uma árvore binária completa com n elementos é calma.
2. Complexidade Espacial
| Complexidade Espacial | O(1) |
| Estábulo | N0 |
- A complexidade do espaço da classificação Heap é O (1).
Implementação de Heapsort
Agora, vamos ver os programas de classificação Heap em diferentes linguagens de programação.
Programa: Escreva um programa para implementar heap sort em linguagem C.
#include /* function to heapify a subtree. Here 'i' is the index of root node in array a[], and 'n' is the size of heap. */ void heapify(int a[], int n, int i) { int largest = i; // Initialize largest as root int left = 2 * i + 1; // left child int right = 2 * i + 2; // right child // If left child is larger than root if (left a[largest]) largest = left; // If right child is larger than root if (right a[largest]) largest = right; // If root is not largest if (largest != i) { // swap a[i] with a[largest] int temp = a[i]; a[i] = a[largest]; a[largest] = temp; heapify(a, n, largest); } } /*Function to implement the heap sort*/ void heapSort(int a[], int n) { for (int i = n / 2 - 1; i >= 0; i--) heapify(a, n, i); // One by one extract an element from heap for (int i = n - 1; i >= 0; i--) { /* Move current root element to end*/ // swap a[0] with a[i] int temp = a[0]; a[0] = a[i]; a[i] = temp; heapify(a, i, 0); } } /* function to print the array elements */ void printArr(int arr[], int n) { for (int i = 0; i <n; ++i) { printf('%d', arr[i]); printf(' '); } int main() a[]="{48," 10, 23, 43, 28, 26, 1}; n="sizeof(a)" sizeof(a[0]); printf('before sorting array elements are -
'); printarr(a, n); heapsort(a, printf('
after return 0; < pre> <p> <strong>Output</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/50/heap-sort-algorithm-20.webp" alt="Heap Sort Algorithm"> <p> <strong>Program:</strong> Write a program to implement heap sort in C++.</p> <pre> #include using namespace std; /* function to heapify a subtree. Here 'i' is the index of root node in array a[], and 'n' is the size of heap. */ void heapify(int a[], int n, int i) { int largest = i; // Initialize largest as root int left = 2 * i + 1; // left child int right = 2 * i + 2; // right child // If left child is larger than root if (left a[largest]) largest = left; // If right child is larger than root if (right a[largest]) largest = right; // If root is not largest if (largest != i) { // swap a[i] with a[largest] int temp = a[i]; a[i] = a[largest]; a[largest] = temp; heapify(a, n, largest); } } /*Function to implement the heap sort*/ void heapSort(int a[], int n) { for (int i = n / 2 - 1; i >= 0; i--) heapify(a, n, i); // One by one extract an element from heap for (int i = n - 1; i >= 0; i--) { /* Move current root element to end*/ // swap a[0] with a[i] int temp = a[0]; a[0] = a[i]; a[i] = temp; heapify(a, i, 0); } } /* function to print the array elements */ void printArr(int a[], int n) { for (int i = 0; i <n; ++i) { cout< <a[i]<<' '; } int main() a[]="{47," 9, 22, 42, 27, 25, 0}; n="sizeof(a)" sizeof(a[0]); cout<<'before sorting array elements are -
'; printarr(a, n); heapsort(a, cout<<'
after return 0; < pre> <p> <strong>Output</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/50/heap-sort-algorithm-21.webp" alt="Heap Sort Algorithm"> <p> <strong>Program:</strong> Write a program to implement heap sort in C#.</p> <pre> using System; class HeapSort { /* function to heapify a subtree. Here 'i' is the index of root node in array a[], and 'n' is the size of heap. */ static void heapify(int[] a, int n, int i) { int largest = i; // Initialize largest as root int left = 2 * i + 1; // left child int right = 2 * i + 2; // right child // If left child is larger than root if (left a[largest]) largest = left; // If right child is larger than root if (right a[largest]) largest = right; // If root is not largest if (largest != i) { // swap a[i] with a[largest] int temp = a[i]; a[i] = a[largest]; a[largest] = temp; heapify(a, n, largest); } } /*Function to implement the heap sort*/ static void heapSort(int[] a, int n) { for (int i = n / 2 - 1; i >= 0; i--) heapify(a, n, i); // One by one extract an element from heap for (int i = n - 1; i >= 0; i--) { /* Move current root element to end*/ // swap a[0] with a[i] int temp = a[0]; a[0] = a[i]; a[i] = temp; heapify(a, i, 0); } } /* function to print the array elements */ static void printArr(int[] a, int n) { for (int i = 0; i <n; ++i) console.write(a[i] + ' '); } static void main() { int[] a="{46," 8, 21, 41, 26, 24, -1}; int n="a.Length;" console.write('before sorting array elements are -
'); printarr(a, n); heapsort(a, console.write('
after < pre> <p> <strong>Output</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/50/heap-sort-algorithm-22.webp" alt="Heap Sort Algorithm"> <p> <strong>Program:</strong> Write a program to implement heap sort in Java.</p> <pre> class HeapSort { /* function to heapify a subtree. Here 'i' is the index of root node in array a[], and 'n' is the size of heap. */ static void heapify(int a[], int n, int i) { int largest = i; // Initialize largest as root int left = 2 * i + 1; // left child int right = 2 * i + 2; // right child // If left child is larger than root if (left a[largest]) largest = left; // If right child is larger than root if (right a[largest]) largest = right; // If root is not largest if (largest != i) { // swap a[i] with a[largest] int temp = a[i]; a[i] = a[largest]; a[largest] = temp; heapify(a, n, largest); } } /*Function to implement the heap sort*/ static void heapSort(int a[], int n) { for (int i = n / 2 - 1; i >= 0; i--) heapify(a, n, i); // One by one extract an element from heap for (int i = n - 1; i >= 0; i--) { /* Move current root element to end*/ // swap a[0] with a[i] int temp = a[0]; a[0] = a[i]; a[i] = temp; heapify(a, i, 0); } } /* function to print the array elements */ static void printArr(int a[], int n) { for (int i = 0; i <n; ++i) system.out.print(a[i] + ' '); } public static void main(string args[]) { int a[]="{45," 7, 20, 40, 25, 23, -2}; n="a.length;" system.out.print('before sorting array elements are -
'); printarr(a, n); heapsort(a, system.out.print('
after < pre> <p> <strong>Output</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/50/heap-sort-algorithm-23.webp" alt="Heap Sort Algorithm"> <p>So, that's all about the article. Hope the article will be helpful and informative to you.</p> <hr></n;></pre></n;></pre></n;></pre></n;>