Como fazer uma atualização prioridade eficiente na priority_queue STL?

Question

Eu tenho um priority_queue de algum objeto:

typedef priority_queue<Object> Queue;
Queue queue;

De tempos em tempos, a prioridade de um dos objetos podem mudar - eu preciso ser capaz de atualizar a prioridade desse objeto na fila de uma forma eficiente. Atualmente estou usando esse método que funciona, mas parece ineficiente:

Queue newQueue;
while (!queue.empty())
{
  Object obj=queue.top();
  queue.pop();

  if (priorityHasChanged(obj))
    newQueue.push_back(Object(new_priority));
  else
    newQueue.push_back(obj);
}

newQueue.swap(queue); // this only works because I actually subclassed the priority_queue
                 // class and exposed a swap method that swaps in the container

Eu implementado desta maneira porque eu estava em uma espécie de pressa na hora e isso era a coisa mais rápida que eu poderia fazer que eu poderia ter certeza de que iria funcionar ok. Tem que haver uma maneira melhor do que isso embora. Realmente o que eu quero é uma maneira de qualquer um:

• extrair a instância com a prioridade mudou e inserir um novo com o novo valor de prioridade
• atualizar a instância com a prioridade mudou e, em seguida, atualizar a fila para que ele seja corretamente ordenada

Qual é a melhor maneira de fazer isso?

Answer 1

Eu acho que você está fora de sorte com fila de prioridade padrão, porque você não pode ficar no deque / vetor / list subjacente ou o que quer. Você precisa implementar o seu próprio -. Não é tão difícil

Answer 2

Posso sugerir 2 opções para resolver o problema, embora nem executa uma atualização real.

1. Use o priority_queue e empurrar elemento de cada vez que você gostaria de atualizá-lo. Aceite o fato de que você terá entradas inúteis na fila. Quando estalar o valor superior, verifique se ele contém o valor up-to-date. Se não, ignorá-lo e colocar o seguinte.

   Desta forma, você atrasar a remoção do elemento atualizado até chegar ao topo. Notei esta abordagem que está sendo usado pelos melhores programadores percebendo algoritmo Dijkstra.

2. Use set. Ele também é classificada assim que você é capaz de extrair o maior elemento em tempo logarítmica. Você também são capazes de remover o elemento ultrapassada antes de inseri-lo novamente. Então, ainda sem operação de atualização possível, mas a remoção e reinserção é factível.

Parece que a complexidade de ambas as abordagens é a mesma.

Answer 3

A maneira mais simples de fazer isso com STL (que eu saiba) é para remover a entrada, actualizar a sua prioridade e, em seguida, insira-o novamente. Fazer isso é bastante lento usando std :: priority_queue, no entanto, você pode fazer a mesma coisa com std :: set. Infelizmente você tem que ter cuidado para não alterar a prioridade de um objeto quando ele está no conjunto.

Eu implementei uma classe mutable_priority_queue baseado colando um std :: multimap (para prioridade para o mapeamento de valor) e um std :: map (para o valor para o mapeamento de prioridade) que lhe permite inserir / itens remove, bem como atualização existente valores em tempo logarítmica. Você pode obter o código e um exemplo de como usá-lo aqui

Answer 4

A estrutura de dados apropriada é chamado de "Fibonacci Heap". Mas você precisa implementá-lo. Inserir / actualizações são O (1) ExtractMin é O (log n)

Answer 5

Eu tenho implementado um alto desempenho atualizável fila de prioridade e disponibilizado no github .

Esta é a forma como você normalmente usá-lo:

better_priority_queue::updatable_priority_queue<int,int> pQ;
pQ.push(0, 30);   // or pQ.set(0, 30)
pQ.push(1, 20);
pQ.push(2, 10);

pQ.update(2, 25); // or pQ.set(2, 25)

while(!pQ.empty())
    std::cout << pQ.pop_value().key << ' ';

// Outputs: 0 2 1

Para complementar a resposta de Jarekczek, se de fato tanto o set e "pilha puro, com entradas inúteis" abordagens têm a mesma complexidade, a versão stl::set normalmente executa muito mais lento do que a versão stl::priority_queue devido ao fato de que ele é implementado com vermelho-preto árvores que só garantem a sua profundidade para ser inferior a 2 log_2 * (n_elements) e exigem atualizações regulares, enquanto stl::priority_queue é um como pilha pura e rápido binário possível. É por isso que é normalmente utilizado na implementação de Dijkstra.

A abordagem conjunto pode, contudo, ser mais rápido ao fazer uma série de atualizações sobre alguns nós de base. Esta é também onde usando minha biblioteca iria trazer-lhe a maioria de melhoria.

Answer 6

Você pode querer ter um olhar para replace_if com um exemplo aqui .

Answer 7

Infelizmente não é possível atualizar o valor em priority_queue. não priority_queue não oferecer tal interface.

Eu acho que você seria melhor uso set como Jarekczek dito ou uso esta solução (usando make_heap).