Heap Sort: Como Funciona, Animação e Código em C, Python e Java

O Heap Sort organiza o vetor como um max-heap, uma árvore binária em que cada pai é maior que seus filhos, guardada no próprio vetor. O maior elemento fica sempre na raiz: basta trocá-lo com o último, diminuir o heap e reorganizar.

Como o Heap Sort Funciona

Transforme o vetor em um max-heap, ajustando os nós de baixo para cima.
Troque a raiz (o maior elemento) com o último elemento do heap.
Diminua o tamanho do heap em 1: o último elemento já está na posição final.
Faça a nova raiz descer até o lugar certo (heapify).
Repita até o heap ter 1 elemento.

Complexidade do Heap Sort

Melhor caso	Caso médio	Pior caso	Memória extra	Estável?
O(n log n)	O(n log n)	O(n log n)	O(1)	Não

Quando usar

Quando é preciso garantir O(n log n) sem usar memória extra. Na prática costuma ser mais lento que o Quick Sort por acessar a memória de forma espalhada, mas é usado como plano B no Introsort.

Heap Sort em C

void descer(int v[], int n, int i) {
    int maior = i, e = 2 * i + 1, d = 2 * i + 2;
    if (e < n && v[e] > v[maior]) maior = e;
    if (d < n && v[d] > v[maior]) maior = d;
    if (maior != i) {
        int aux = v[i]; v[i] = v[maior]; v[maior] = aux;
        descer(v, n, maior);
    }
}

void heap_sort(int v[], int n) {
    for (int i = n / 2 - 1; i >= 0; i--) descer(v, n, i);
    for (int fim = n - 1; fim > 0; fim--) {
        int aux = v[0]; v[0] = v[fim]; v[fim] = aux;
        descer(v, fim, 0);
    }
}

Heap Sort em Python

def descer(v, n, i):
    maior, e, d = i, 2 * i + 1, 2 * i + 2
    if e < n and v[e] > v[maior]:
        maior = e
    if d < n and v[d] > v[maior]:
        maior = d
    if maior != i:
        v[i], v[maior] = v[maior], v[i]
        descer(v, n, maior)

def heap_sort(v):
    n = len(v)
    for i in range(n // 2 - 1, -1, -1):
        descer(v, n, i)
    for fim in range(n - 1, 0, -1):
        v[0], v[fim] = v[fim], v[0]
        descer(v, fim, 0)
    return v

Heap Sort em Java

static void descer(int[] v, int n, int i) {
    int maior = i, e = 2 * i + 1, d = 2 * i + 2;
    if (e < n && v[e] > v[maior]) maior = e;
    if (d < n && v[d] > v[maior]) maior = d;
    if (maior != i) {
        int aux = v[i]; v[i] = v[maior]; v[maior] = aux;
        descer(v, n, maior);
    }
}

static void heapSort(int[] v) {
    for (int i = v.length / 2 - 1; i >= 0; i--) descer(v, v.length, i);
    for (int fim = v.length - 1; fim > 0; fim--) {
        int aux = v[0]; v[0] = v[fim]; v[fim] = aux;
        descer(v, fim, 0);
    }
}

Quer comparar com outros métodos? No visualizador de algoritmos de ordenação você roda todos no mesmo vetor e compara o número de comparações e trocas.

Perguntas Frequentes

Qual a complexidade do Heap Sort?

O(n log n) em todos os casos. Construir o heap custa O(n), e cada uma das n extrações faz a raiz descer no máximo log n níveis.

O que é um heap?

É uma árvore binária completa guardada em um vetor: os filhos do índice i ficam nos índices 2i + 1 e 2i + 2. Em um max-heap, todo pai é maior ou igual aos filhos, então o maior elemento está sempre no índice 0.

O Heap Sort é estável?

Não. As trocas entre a raiz e o fim do heap podem mudar a ordem relativa de elementos iguais.

Heap Sort: Animação Passo a Passo