Heapsort

---

Até aqui vimos algoritmos de ordenação, que para superar $\theta (n^2)$ usem o paradigma de divisão e conquista (mergesort e quicksort) e com isso rodam no caso médio em $\theta (n\log n)$.k

Há, no entanto, um modo alternativo e muito criativo para um algoritmo superar $\theta (n^2)$: tirar proveito de uma estrutura de dados poderosa para com isso chegar à $\theta (n\log n)$ para o caso médio. O algoritmo que veremos a seguir roda em $O(n\log n)$ e faz isso localmente ($O(1)$ de eficiência no espaço).

Heap-max

Uma árvore quase completa onde cada nó pai é maior ou igual a suas filhas. Portanto, temos o maior valor acessível de forma imediata na raiz da árvore.

Árvore não pode ser cíclico, ou seja, todas as ramificações devem ter um nó terminal sem que seja ligado a um outro nó.

Exercício

1. Criar 1 max-heap $\theta (n\log n)$ no pior caso.
2. Ordenar usando o max-heap em $O\log n$ para o pior caso.
3. Localmente (sem utilizar uma estrutura externa, tudo no mesmo vetor).
4. De modo não muito complicado.

Referências

---

• UDI Mamber
• Cormen