Por que ultilizar o min_heap?

Por que ultilizar o min_heap?

by Luiz Leonardo Cesar Rodrigues -
Number of replies: 4

Não entendi ao certo a utilidade do min_heap assim como a utilidade da função "peneira" de tal forma que estou com dificuldade de implementá-las.

O algorítimo de gram se baseia em 3 passos:

----------------

para cada tarefa{

encontra a maquina com menor tempo associado;

atribui a tarefa a essa maquina;

};

retorna o escalonamento;

----------------

Assim sendo o algorítimo poderia ser resumido a 2 comandos "for". Estou enganado?

Alguém poderia me auxiliar a entender o por que utilizar o min_heap e a função "peneira"?

In reply to Luiz Leonardo Cesar Rodrigues

Re: Por que ultilizar o min_heap?

by Kaonan Micadei -
Também gostaria de saiber isso.
In reply to Kaonan Micadei

Porque o min-heap é um jeito barato...

by Luciano Ramalho -
...de manter a relação de máquinas arrumada de tal forma que seja fácil acessar aquela que está menos ocupada (ela será sempre a primeira).

A alternativa de buscar toda vez a máquina menos ocupada num vetor desordenado é mais cara, e reordenar um vetor de índices para as máquinas a cada iteração também é caro e desnecessário: você não precisa que todas as máquinas sejam arranjadas em ordem crescente de ocupação, precisa apenas que a menos ocupada seja fácil de encontrar, e isso o min-heap te dá com um mínimo de trabalho de manutenção.

Eu tive a mesma dúvida, mas depois de ler estes dois artigos na wikipedia achei que este deve ser o motivo.

http://en.wikipedia.org/wiki/Binary_heap
http://en.wikipedia.org/wiki/Heap_%28data_structure%29

O prof. pode me corrigir e complementar.
In reply to Luciano Ramalho

Re: Porque o min-heap é um jeito barato...

by Luiz Leonardo Cesar Rodrigues -
Muito obrigado Luciano. Provavelmente é isso mesmo.

Nesse aspecto teriamos um ganho de tempo de "n*m" para "n.logn"...
Para valores pequenos de "n", como os do exercício, não sei se o ganho de tempo seria justificável, levando em consideração a perda de concisão e clareza do EP.

Professor. Haverá perda de nota caso a função Graham seja feita por busca interativa?

In reply to Luiz Leonardo Cesar Rodrigues

Re: Porque o min-heap é um jeito barato...

by Francisco Reverbel -
Luiz Leonardo: "Muito obrigado Luciano. Provavelmente é isso mesmo."

Sim, é isso. Obrigado, Luciano.

Luiz Leonardo: "Nesse aspecto teriamos um ganho de tempo de "n*m" para "n.logn"..."

Uma pequena correção: o ganho de tempo é de O(n * m) para O(n * log m), onde n é o número de tarefas e m o de máquinas.

Luiz Leonardo: "Para valores pequenos de "n", como os do exercício, não sei se o ganho de tempo seria justificável, levando em consideração a perda de concisão e clareza do EP."

Só haverá ganho para valores grandes de m. Num caso como o do exemplo do enunciado (valores de n e m pequenos), o uso de um min-heap não traz nenhuma vantagem.

Note, entretanto, que o problema do escalonamento não restringe os valores de n e de m. Seu programa (pelo menos a parte que implementa o algoritmo de Graham) deve rodar para instâncias grandes do problema do escalonamento. A ressalva (só "a parte que implementa o algoritimo de Graham") é porque para instâncias grandes a busca exaustiva leva um tempo proibitivo: na prática ela não acaba nunca! Isso acontece mesmo para instâncias de tamanho moderado. Mas a o algoritmo de Graham deve rodar bem para instâncias grandes (com os números de tarefas e de máquinas na casa dos milhares ou milhões).

Luiz Leonardo: "Professor. Haverá perda de nota caso a função Graham seja feita por busca interativa?"

Sim.