Heapsort §

---

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

Há, no entanto, um modo alternativo e muito criativo para um algoritmo superar : tirar proveito de uma estrutura de dados poderosa para com isso chegar à para o caso médio. O algoritmo que veremos a seguir roda em e faz isso localmente ( 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 no pior caso.
2. Ordenar usando o max-heap em 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