Jump to content

Duvidas num exercicio de Heaps


mcj
 Share

Recommended Posts

Realize a classe generica KeyedPriorityQueue<E>, que implementa uma fila de prioridades baseada em

amontoados binarios, contendo os seguintes metodos:

public int add(E elem, int prio) - adiciona o elemento elem, com prioridade prio, a fila. Este

metodo retorna um inteiro, designado por chave do elemento.

Cada elemento presente na fila e representado por um inteiro, designado de chave, gerado e retornado pelo

metodo add. A chave de cada elemento e constante, não variando com mudanca de posição relativa do

elemento no amontoado binario.

Sugere-se que a classe possua internamente uma tabela que associa a

cada chave o indice no amontoado binario do elemento representado. Todas as operações que alteram indices

de elementos devem actualizar esta tabela.

O custo de todos os metodos deve pertencer a O(lg n), onde n representa o numero de elementos na fila.

O que querem dizer com prioridade 'prio'? 'Prio' é um indice ou chave em k apartir desse indice ou chave tenho k ordenar o heap?

Link to comment
Share on other sites

Percorres a fila até encontrares a posição de valor de prioridade imediatamente acima do que queres inserir.

Não estás a usar nós ou algo assim parecido? Se estiveres é fácil, senão vais ter que redimensionar a fila andando um indice para frente a cada elemento a seguir ao que queres inserir.

Link to comment
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now
 Share

×
×
  • Create New...

Important Information

By using this site you accept our Terms of Use and Privacy Policy. We have placed cookies on your device to help make this website better. You can adjust your cookie settings, otherwise we'll assume you're okay to continue.