Neste tutorial, você aprenderá como o algoritmo de classificação de heap funciona. Além disso, você encontrará exemplos funcionais de classificação de heap em C, C ++, Java e Python.
Heap Sort é um algoritmo de classificação popular e eficiente em programação de computadores. Aprender como escrever o algoritmo de classificação de heap requer o conhecimento de dois tipos de estruturas de dados - arrays e árvores.
O conjunto inicial de números que queremos classificar é armazenado em um array, por exemplo, (10, 3, 76, 34, 23, 32)e após a classificação, obtemos um array ordenado(3,10,23,32,34,76)
A classificação de heap funciona visualizando os elementos do array como um tipo especial de árvore binária completa chamada heap.
Como pré-requisito, você deve conhecer uma árvore binária completa e uma estrutura de dados de heap.
Relação entre índices de matriz e elementos de árvore
Uma árvore binária completa tem uma propriedade interessante que podemos usar para encontrar os filhos e pais de qualquer nó.
Se o índice de qualquer elemento na matriz for i, o elemento no índice 2i+1se tornará o filho esquerdo e o elemento no 2i+2índice se tornará o filho direito. Além disso, o pai de qualquer elemento no índice i é dado pelo limite inferior de (i-1)/2.
Relação entre matriz e índices de heap
Vamos testar,
Filho esquerdo de 1 (índice 0) = elemento em (2 * 0 + 1) índice = elemento em 1 índice = 12 Filho direito de 1 = elemento em (2 * 0 + 2) índice = elemento em 2 índice = 9 Da mesma forma, Filho esquerdo de 12 (índice 1) = elemento em (2 * 1 + 1) índice = elemento em 3 índice = 5 Filho direito de 12 = elemento em (2 * 1 + 2) índice = elemento em 4 índice = 6
Vamos também confirmar que as regras são válidas para encontrar o pai de qualquer nó
Pai de 9 (posição 2) = (2-1) / 2 = ½ = 0,5 ~ 0 índice = 1 Pai de 12 (posição 1) = (1-1) / 2 = 0 índice = 1
Entender esse mapeamento de índices de array para posições de árvore é crítico para entender como a Estrutura de Dados Heap funciona e como ela é usada para implementar Heap Sort.
O que é Heap Data Structure?
Heap é uma estrutura de dados especial baseada em árvore. Diz-se que uma árvore binária segue uma estrutura de dados heap se
- é uma árvore binária completa
- Todos os nós na árvore seguem a propriedade de serem maiores do que seus filhos, ou seja, o maior elemento está na raiz e seus filhos são menores do que a raiz e assim por diante. Esse heap é chamado de heap máximo. Se, em vez disso, todos os nós são menores que seus filhos, é chamado de min-heap
O diagrama de exemplo a seguir mostra Max-Heap e Min-Heap.
Pilha máxima e pilha mínima
Para saber mais sobre isso, visite Heap Data Structure.
Como "heapificar" uma árvore
Começando com uma árvore binária completa, podemos modificá-la para se tornar um Max-Heap executando uma função chamada heapify em todos os elementos não-folha do heap.
Como o heapify usa recursão, pode ser difícil de entender. Portanto, vamos primeiro pensar sobre como você iria heapificar uma árvore com apenas três elementos.
heapify(array) Root = array(0) Largest = largest( array(0) , array (2*0 + 1). array(2*0+2)) if(Root != Largest) Swap(Root, Largest) 
Heapify casos básicos
O exemplo acima mostra dois cenários - um em que a raiz é o maior elemento e não precisamos fazer nada. E outro em que a raiz tinha um elemento maior como filho e precisávamos trocar para manter a propriedade de heap máximo.
Se você já trabalhou com algoritmos recursivos antes, provavelmente identificou que esse deve ser o caso básico.
Agora vamos pensar em outro cenário no qual existe mais de um nível.
Como heapificar o elemento raiz quando suas subárvores já são pilhas máximas
O elemento superior não é um heap máximo, mas todas as subárvores são heap máximo.
Para manter a propriedade de heap máximo para a árvore inteira, teremos que continuar empurrando 2 para baixo até que alcance sua posição correta.
Como heapificar o elemento raiz quando suas subárvores são pilhas máximas
Portanto, para manter a propriedade max-heap em uma árvore onde ambas as subárvores são max-heaps, precisamos executar heapify no elemento raiz repetidamente até que ele seja maior do que seus filhos ou se torne um nó folha.
Podemos combinar essas duas condições em uma função heapify como
void heapify(int arr(), int n, int i) ( // Find largest among root, left child and right child int largest = i; int left = 2 * i + 1; int right = 2 * i + 2; if (left arr(largest)) largest = left; if (right arr(largest)) largest = right; // Swap and continue heapifying if root is not largest if (largest != i) ( swap(&arr(i), &arr(largest)); heapify(arr, n, largest); ) )
Esta função funciona tanto para o caso base quanto para uma árvore de qualquer tamanho. Podemos, portanto, mover o elemento raiz para a posição correta para manter o status de heap máximo para qualquer tamanho de árvore, desde que as subárvores sejam de heap máximo.
Construir pilha máxima
Para construir um heap máximo a partir de qualquer árvore, podemos começar a heapificar cada subárvore de baixo para cima e terminar com um heap máximo depois que a função for aplicada a todos os elementos, incluindo o elemento raiz.
No caso de uma árvore completa, o primeiro índice de um nó não folha é dado por n/2 - 1. Todos os outros nós posteriores são nós folha e, portanto, não precisam ser heapificados.
Então, podemos construir um heap máximo como
// Build heap (rearrange array) for (int i = n / 2 - 1; i>= 0; i--) heapify(arr, n, i); 
Criar matriz e calcular i 
Etapas para construir heap máximo para classificação de heap 
Etapas para construir heap máximo para classificação de heap 
Etapas para construir heap máximo para classificação de heap
Conforme mostrado no diagrama acima, começamos por heapificar as árvores menores mais baixas e subir gradualmente até chegarmos ao elemento raiz.
Se você entendeu tudo até aqui, parabéns, você está prestes a dominar o tipo Heap.
Como funciona a classificação de heap?
- Como a árvore satisfaz a propriedade Max-Heap, o maior item é armazenado no nó raiz.
- Trocar: Remova o elemento raiz e coloque no final do array (enésima posição) Coloque o último item da árvore (heap) no local vago.
- Remover: reduza o tamanho da pilha em 1.
- Heapify: Heapify o elemento raiz novamente para que tenhamos o elemento mais alto na raiz.
- O processo é repetido até que todos os itens da lista sejam classificados.
Trocar, Remover e Heapify
O código abaixo mostra a operação.
// Heap sort for (int i = n - 1; i>= 0; i--) ( swap(&arr(0), &arr(i)); // Heapify root element to get highest element at root again heapify(arr, i, 0); )
Exemplos de Python, Java e C / C ++
Python Java C C ++ # Heap Sort in python def heapify(arr, n, i): # Find largest among root and children largest = i l = 2 * i + 1 r = 2 * i + 2 if l < n and arr(i) < arr(l): largest = l if r < n and arr(largest) < arr(r): largest = r # If root is not largest, swap with largest and continue heapifying if largest != i: arr(i), arr(largest) = arr(largest), arr(i) heapify(arr, n, largest) def heapSort(arr): n = len(arr) # Build max heap for i in range(n//2, -1, -1): heapify(arr, n, i) for i in range(n-1, 0, -1): # Swap arr(i), arr(0) = arr(0), arr(i) # Heapify root element heapify(arr, i, 0) arr = (1, 12, 9, 5, 6, 10) heapSort(arr) n = len(arr) print("Sorted array is") for i in range(n): print("%d " % arr(i), end='')
// Heap Sort in Java public class HeapSort ( public void sort(int arr()) ( int n = arr.length; // Build max heap for (int i = n / 2 - 1; i>= 0; i--) ( heapify(arr, n, i); ) // Heap sort for (int i = n - 1; i>= 0; i--) ( int temp = arr(0); arr(0) = arr(i); arr(i) = temp; // Heapify root element heapify(arr, i, 0); ) ) void heapify(int arr(), int n, int i) ( // Find largest among root, left child and right child 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; // Swap and continue heapifying if root is not largest if (largest != i) ( int swap = arr(i); arr(i) = arr(largest); arr(largest) = swap; heapify(arr, n, largest); ) ) // Function to print an array static void printArray(int arr()) ( int n = arr.length; for (int i = 0; i < n; ++i) System.out.print(arr(i) + " "); System.out.println(); ) // Driver code public static void main(String args()) ( int arr() = ( 1, 12, 9, 5, 6, 10 ); HeapSort hs = new HeapSort(); hs.sort(arr); System.out.println("Sorted array is"); printArray(arr); ) )
// Heap Sort in C #include // Function to swap the the position of two elements void swap(int *a, int *b) ( int temp = *a; *a = *b; *b = temp; ) void heapify(int arr(), int n, int i) ( // Find largest among root, left child and right child int largest = i; int left = 2 * i + 1; int right = 2 * i + 2; if (left arr(largest)) largest = left; if (right arr(largest)) largest = right; // Swap and continue heapifying if root is not largest if (largest != i) ( swap(&arr(i), &arr(largest)); heapify(arr, n, largest); ) ) // Main function to do heap sort void heapSort(int arr(), int n) ( // Build max heap for (int i = n / 2 - 1; i>= 0; i--) heapify(arr, n, i); // Heap sort for (int i = n - 1; i>= 0; i--) ( swap(&arr(0), &arr(i)); // Heapify root element to get highest element at root again heapify(arr, i, 0); ) ) // Print an array void printArray(int arr(), int n) ( for (int i = 0; i < n; ++i) printf("%d ", arr(i)); printf(""); ) // Driver code int main() ( int arr() = (1, 12, 9, 5, 6, 10); int n = sizeof(arr) / sizeof(arr(0)); heapSort(arr, n); printf("Sorted array is "); printArray(arr, n); )
// Heap Sort in C++ #include using namespace std; void heapify(int arr(), int n, int i) ( // Find largest among root, left child and right child int largest = i; int left = 2 * i + 1; int right = 2 * i + 2; if (left arr(largest)) largest = left; if (right arr(largest)) largest = right; // Swap and continue heapifying if root is not largest if (largest != i) ( swap(arr(i), arr(largest)); heapify(arr, n, largest); ) ) // main function to do heap sort void heapSort(int arr(), int n) ( // Build max heap for (int i = n / 2 - 1; i>= 0; i--) heapify(arr, n, i); // Heap sort for (int i = n - 1; i>= 0; i--) ( swap(arr(0), arr(i)); // Heapify root element to get highest element at root again heapify(arr, i, 0); ) ) // Print an array void printArray(int arr(), int n) ( for (int i = 0; i < n; ++i) cout << arr(i) << " "; cout << ""; ) // Driver code int main() ( int arr() = (1, 12, 9, 5, 6, 10); int n = sizeof(arr) / sizeof(arr(0)); heapSort(arr, n); cout << "Sorted array is "; printArray(arr, n); )
Complexidade de classificação de heap
A classificação de heap tem O(nlog n)complexidades de tempo para todos os casos (melhor caso, caso médio e pior caso).
Vamos entender o motivo. A altura de uma árvore binária completa contendo n elementos élog n
As we have seen earlier, to fully heapify an element whose subtrees are already max-heaps, we need to keep comparing the element with its left and right children and pushing it downwards until it reaches a point where both its children are smaller than it.
In the worst case scenario, we will need to move an element from the root to the leaf node making a multiple of log(n) comparisons and swaps.
During the build_max_heap stage, we do that for n/2 elements so the worst case complexity of the build_heap step is n/2*log n ~ nlog n.
During the sorting step, we exchange the root element with the last element and heapify the root element. For each element, this again takes log n worst time because we might have to bring the element all the way from the root to the leaf. Since we repeat this n times, the heap_sort step is also nlog n.
Also since the build_max_heap and heap_sort steps are executed one after another, the algorithmic complexity is not multiplied and it remains in the order of nlog n.
Also it performs sorting in O(1) space complexity. Compared with Quick Sort, it has a better worst case ( O(nlog n) ). Quick Sort has complexity O(n^2) for worst case. But in other cases, Quick Sort is fast. Introsort is an alternative to heapsort that combines quicksort and heapsort to retain advantages of both: worst case speed of heapsort and average speed of quicksort.
Heap Sort Applications
Systems concerned with security and embedded systems such as Linux Kernel use Heap Sort because of the O(n log n) upper bound on Heapsort's running time and constant O(1) upper bound on its auxiliary storage.
Embora o Heap Sort tenha O(n log n)complexidade de tempo, mesmo para o pior caso, ele não tem mais aplicativos (em comparação com outros algoritmos de classificação como Quick Sort, Merge Sort). No entanto, sua estrutura de dados subjacente, heap, pode ser usada com eficiência se quisermos extrair o menor (ou o maior) da lista de itens sem a sobrecarga de manter os itens restantes na ordem de classificação. Por exemplo, filas prioritárias.
