Partial Heapsort

Aqui nada de estranho: inicialmente cria-se um heap_invertido. Faz-se k vezes o o passo de remoção do raiz da heap para o final da fila. Ao final da ordenação dos k elementos , estes, que estavam em ordem reversa ao no final do vertor, são copiado de volta.

• O custo para montar o heap é o mesmo:
• O custo apra retirar os k primeiros: m)
• O custo para re-ordenar os k elementos no incio do vertor:

Total: =

Um pequeno ajuda mas o estará sempre presente.