Heap Sort
Última atualização
O heap sort trata o array como um heap binário. Primeiro ele constrói um max-heap, de modo que o maior elemento fica na raiz (índice 0). Depois troca repetidamente a raiz com o último elemento não ordenado - fixando o máximo no lugar - e afunda a nova raiz para restaurar a propriedade do heap. Pressione reproduzir acima para ver a construção do heap e as extrações.
O heap sort garante tempo O(n log n) como o merge sort, mas ordena no local com apenas O(1) de espaço extra. Não é estável e tende a ter pior comportamento de cache que o quicksort, por isso costuma ser escolhido quando tanto um limite garantido quanto memória constante importam.
Complexidade de tempo e espaço
| Caso | Complexidade | Notas |
|---|---|---|
| Melhor caso | O(n log n) | Construção + n extrações |
| Caso médio | O(n log n) | Ordem aleatória |
| Pior caso | O(n log n) | Garantido |
| Espaço | O(1) | No local |
| Estável | Não | O afundamento reordena elementos iguais |
Passo a passo
| Passo | O que acontece |
|---|---|
| 1 | Construir um max-heap a partir do array (afundar a partir do último pai). |
| 2 | Trocar a raiz (máximo) com o último elemento do heap. |
| 3 | Reduzir o heap em um - aquele último espaço agora está ordenado. |
| 4 | Afundar a nova raiz para restaurar a propriedade do max-heap. |
| 5 | Repetir até o heap ter um único elemento. |
Exemplo resolvido
Ordenando [3, 1, 6, 5, 2, 4]. A barra | marca o limite entre o heap que encolhe e a cauda ordenada:
| Passagem | Array | Ação |
|---|---|---|
| Construir heap | [6, 5, 4, 1, 2, 3] | Afundar a partir do último pai para construir o max-heap; 6 agora está na raiz. |
| 1 | [5, 3, 4, 1, 2 | 6] | Trocar a raiz 6 com o último espaço, reduzir o heap e afundar 3. |
| 2 | [4, 3, 2, 1 | 5, 6] | Retirar a raiz 5, depois afundar 2 para que 4 suba à raiz. |
| 3 | [3, 1, 2 | 4, 5, 6] | Retirar a raiz 4, depois afundar 1 para que 3 suba à raiz. |
| 4 | [2, 1 | 3, 4, 5, 6] | Retirar a raiz 3; 2 já satisfaz a propriedade do heap. |
| 5 | [1 | 2, 3, 4, 5, 6] | Retirar a raiz 2; resta um elemento, então o array está ordenado. |
Quando usar o heap sort
| Use quando | Evite quando |
|---|---|
Você precisa de um pior caso garantido de O(n log n) sem risco de O(n²). | Você precisa de uma ordenação estável que preserve a ordem de chaves iguais. |
A memória é escassa - ordena no local com apenas O(1) de espaço extra. | O desempenho de cache importa e os dados cabem na memória - o quicksort costuma ser mais rápido. |
| Você já mantém um heap (por exemplo, uma fila de prioridade) sobre os dados. | Você quer o menor número de comparações - merge sort e quicksort costumam fazer menos na prática. |
| Uma entrada não confiável poderia disparar o pior caso do quicksort e você não pode aleatorizar. | Os dados estão quase ordenados - o insertion sort roda em tempo quase linear sobre eles. |
Código de Heap Sort
Uma implementação limpa e executável de Heap Sort em Python, JavaScript, Java, C++, C. Escolha uma linguagem, copie o código ou abra-o já carregado no Playground da Coddy.
Código de Heap Sort em Python
Python
1def heap_sort(a):2 n = len(a)3 # Build a max-heap, deepest parent first4 for i in range(n // 2 - 1, -1, -1):5 sift_down(a, i, n)6 # Repeatedly move the max to the end and shrink the heap7 for end in range(n - 1, 0, -1):8 a[0], a[end] = a[end], a[0]9 sift_down(a, 0, end)10 return a11
12
13def sift_down(a, i, size):14 while True:15 largest = i16 left, right = 2 * i + 1, 2 * i + 217 if left < size and a[left] > a[largest]:18 largest = left19 if right < size and a[right] > a[largest]:20 largest = right21 if largest == i:22 return23 a[i], a[largest] = a[largest], a[i]24 i = largest25
26
27nums = [12, 11, 13, 5, 6, 7]28print("Before:", nums)29heap_sort(nums)30print("After: ", nums)Código de Heap Sort em JavaScript
JavaScript
1function heapSort(a) {2 const n = a.length;3 // Build a max-heap, then repeatedly move the max to the end4 for (let i = Math.floor(n / 2) - 1; i >= 0; i--) siftDown(a, i, n);5 for (let end = n - 1; end > 0; end--) {6 [a[0], a[end]] = [a[end], a[0]];7 siftDown(a, 0, end);8 }9 return a;10}11
12function siftDown(a, i, size) {13 while (true) {14 const left = 2 * i + 1;15 const right = 2 * i + 2;16 let largest = i;17 if (left < size && a[left] > a[largest]) largest = left;18 if (right < size && a[right] > a[largest]) largest = right;19 if (largest === i) return;20 [a[i], a[largest]] = [a[largest], a[i]];21 i = largest;22 }23}24
25const data = [5, 2, 9, 1, 7, 3];26console.log("Before:", data);27console.log("Sorted:", heapSort([...data]));Código de Heap Sort em Java
Java
1import java.util.Arrays;2
3public class Main {4 static void heapSort(int[] arr) {5 int n = arr.length;6 // Build a max-heap, deepest parent first7 for (int i = n / 2 - 1; i >= 0; i--) siftDown(arr, i, n);8 // Repeatedly move the max to the end and shrink the heap9 for (int end = n - 1; end > 0; end--) {10 swap(arr, 0, end);11 siftDown(arr, 0, end);12 }13 }14
15 static void siftDown(int[] arr, int i, int size) {16 while (true) {17 int largest = i, l = 2 * i + 1, r = 2 * i + 2;18 if (l < size && arr[l] > arr[largest]) largest = l;19 if (r < size && arr[r] > arr[largest]) largest = r;20 if (largest == i) return;21 swap(arr, i, largest);22 i = largest;23 }24 }25
26 static void swap(int[] arr, int a, int b) {27 int tmp = arr[a];28 arr[a] = arr[b];29 arr[b] = tmp;30 }31
32 public static void main(String[] args) {33 int[] arr = {12, 11, 13, 5, 6, 7};34 System.out.println("Before: " + Arrays.toString(arr));35 heapSort(arr);36 System.out.println("After: " + Arrays.toString(arr));37 }38}Código de Heap Sort em C++
C++
1#include <iostream>2#include <utility>3#include <vector>4
5void printVec(const std::vector<int>& a) {6 for (int x : a) std::cout << x << " ";7 std::cout << "\n";8}9
10void siftDown(std::vector<int>& a, int n, int i) {11 while (true) {12 int largest = i, l = 2 * i + 1, r = 2 * i + 2;13 if (l < n && a[l] > a[largest]) largest = l;14 if (r < n && a[r] > a[largest]) largest = r;15 if (largest == i) return;16 std::swap(a[i], a[largest]);17 i = largest;18 }19}20
21void heapSort(std::vector<int>& a) {22 int n = static_cast<int>(a.size());23 // Build a max-heap in place24 for (int i = n / 2 - 1; i >= 0; --i) siftDown(a, n, i);25 // Repeatedly move the max to the end and shrink the heap26 for (int end = n - 1; end > 0; --end) {27 std::swap(a[0], a[end]);28 siftDown(a, end, 0);29 }30}31
32int main() {33 std::vector<int> data = {12, 11, 13, 5, 6, 7};34 std::cout << "Before: ";35 printVec(data);36 heapSort(data);37 std::cout << "After: ";38 printVec(data);39 return 0;40}Código de Heap Sort em C
C
1#include <stdio.h>2
3void printArr(const int a[], int n) {4 for (int i = 0; i < n; i++) printf("%d ", a[i]);5 printf("\n");6}7
8void siftDown(int a[], int n, int i) {9 while (1) {10 int largest = i, l = 2 * i + 1, r = 2 * i + 2;11 if (l < n && a[l] > a[largest]) largest = l;12 if (r < n && a[r] > a[largest]) largest = r;13 if (largest == i) return;14 int tmp = a[i];15 a[i] = a[largest];16 a[largest] = tmp;17 i = largest;18 }19}20
21void heapSort(int a[], int n) {22 // Build a max-heap in place23 for (int i = n / 2 - 1; i >= 0; i--) siftDown(a, n, i);24 // Repeatedly move the max to the end and shrink the heap25 for (int end = n - 1; end > 0; end--) {26 int tmp = a[0];27 a[0] = a[end];28 a[end] = tmp;29 siftDown(a, end, 0);30 }31}32
33int main(void) {34 int data[] = {12, 11, 13, 5, 6, 7};35 int n = sizeof(data) / sizeof(data[0]);36 printf("Before: ");37 printArr(data, n);38 heapSort(data, n);39 printf("After: ");40 printArr(data, n);41 return 0;42}Perguntas frequentes sobre Heap Sort
Qual é a complexidade de tempo do heap sort?
O heap sort é
O(n log n) no melhor, no médio e no pior caso. Construir o heap é O(n) e cada uma das n extrações custa O(log n). Ele usa O(1) de espaço extra.O heap sort é estável?
Não. A operação de afundamento pode mover elementos iguais uns sobre os outros, então o heap sort não preserva a ordem relativa de chaves iguais.
Quando devo usar o heap sort?
Use o heap sort quando precisar de um pior caso garantido de
O(n log n) com apenas O(1) de memória extra. Ele evita o risco de O(n²) do quicksort sem o buffer de O(n) do merge sort, ao custo de estabilidade e desempenho de cache.Qual é a diferença entre heap sort e quicksort?
Ambos ordenam no local, mas o quicksort tem um pior caso de
O(n²) enquanto o heap sort garante O(n log n). Na prática o quicksort costuma ser mais rápido por causa da melhor localidade de cache e menos trocas, então o heap sort é preferido principalmente quando o limite do pior caso precisa ser garantido.Como o heap sort se relaciona com uma fila de prioridade?
Um heap binário é a implementação padrão de uma fila de prioridade, e o heap sort consiste essencialmente em retirar repetidamente o máximo dessa fila. Se você já mantém seus dados em um heap, extrair os elementos um a um lhe dá a ordem ordenada de graça.
O heap sort precisa de um max-heap ou de um min-heap?
Para ordenar em ordem crescente no local, use um max-heap: o maior elemento é trocado para o fim em cada passagem, fazendo a cauda ordenada crescer a partir da direita. Um min-heap produziria ordem decrescente no local, ou crescente se você extrair para um array separado.
Recursos relacionados
Mais visualizações
