heap sort

The heapsort algorithm can be divided into two partes
- Step 1: a heap is built out of the data
- Step 2: a sorted array is created by repeatedly removing the largest element from the heap, and inserting it into the array.

The heap is reconstructed after each removal. Once all objects have been removed from the heap, we have a sorted array. The direction of the sorted elements can be varied by chossing a min-heap or mar-heap in the step one.

Complexity: O(n.log n)

Design algoritmica

-> Divisão e conquista (divide and conquer)
->Atacar/resolver um problema algorítmico em que a dimensão dos dados de entrada é N através  da divisão dos dados de entrada em partes mais pequenas (duas ou mais partes), aplicar a resolução (geralmente de modo recursivo )a cada uma das partes e finalmente fazer a combinação dos resultados obtidos de modo a obter a solução final.

Etapas:

1) Divisão dos dados N => P1,P2...
2) Conquista/resolução a cada uma das partes Pi
3)Combinação dos resultados para obter solução final

 Processo de divisão e conquista/recursivo) aplicado em ordenação por partes(merge sort)