• Revista PROGRAMAR: Já está disponível a edição #53 da revista programar. Faz já o download aqui!

iptleic

AJUDA - Heapsort

10 mensagens neste tópico

Boas,

Pessoal eu não percebo o funcionamento duma heapsort.. alguem me ajuda?nem k seja so explicando assim por alto como funciona.. e como funciona o fixdown?i o fixup?

EDIT:usar titulos descritivos ( pedrotuga )

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Podias era dar títulos mais sugestivos e não repetir pedidos.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Se queres saber como funciona o heap sort vou partir do princípio que já sabes o que é uma heap.

Basicamente, atiras todos os elementos que queres ordenar para dentro da heap, e removes elemento a elemento no final.

Ou seja, para um vector de n elementos, n pushes e n pops, o que dá um total de O(2x n*logn) no pior dos casos.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Ou seja, para um vector de n elementos, n pushes e n pops, o que dá um total de O(2x n*logn) no pior dos casos.

Se os elementos já estiverem num array pode-se criar logo a heap em O(n) e fazer os restantes passos em O(nlog n).

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Como é que partindo de um vector crias uma heap em O(n)?

Precisas de pelo menos O(n) para percorrer o vector e O(log n) para inserir cada um deles.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

O tempo de execução da função que coloca/insere cada elemento no sitio certo na heap não é constante, vai variando. Os primeiros elementos vão ser colocados mais depressa que os últimos, pois a altura da heap vai aumentando. Isso permite calcular um limite assimptótico mais baixo, O(n). No "Introduction to Algorithms" existe uma explicação formal em que se demonstra esse limite.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

http://www.faqs.org/docs/thinkjava/chap18.htm -> "HeapSort" ; referência a O(n logn)

http://en.wikipedia.org/wiki/Heap_sort -> Same

Não se pode desprezar o log n na inserção, apesar de não ser completo.

Isso seria o mesmo que dizer que o bubble sort, uma vez que na segunda passagem não percorre todos os elementos mas sim só metade, tem uma complexidade O(n) em vez de O(n²).

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Eu estava-me a referir à criação da heap, não à ordenação propriamente dita. No livro que referi isso está demonstrado.

We can compute a simple upper bound on the running time of BUILD-MAX-HEAP as follows. Each call to MAX-HEAPIFY costs O(lg n) time, and there are O(n) such calls. Thus, the running time is O(n lg n). This upper bound, though correct, is not asymptotically tight.

We can derive a tighter bound by observing that the time for MAX-HEAPIFY to run at a node varies with the height of the node in the tree, and the heights of most nodes are small.

Depois da demonstração (como tem somatorios não a coloco aqui, acho que não ficaria muito legível):

Hence, we can build a max-heap from an unordered array in linear time.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Já tinha percebido onde querias chegar, mas contínuo a achar que considerar a criação O(n) é bastante exagerado (como sempre, depende dos casos de teste, isso só funciona para casos específicos).

De qualquer das formas o autor do tópico queria perceber como funciona o heap sort, não a complexidade dele.. E nunca mais apareceu.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Crie uma conta ou ligue-se para comentar

Só membros podem comentar

Criar nova conta

Registe para ter uma conta na nossa comunidade. É fácil!


Registar nova conta

Entra

Já tem conta? Inicie sessão aqui.


Entrar Agora