Atualizando o Java PriorityQueue quando seus elementos mudam de prioridade

Eu estou tentando usar um PriorityQueue para ordenar objects usando um Comparator .

Isso pode ser feito facilmente, mas as variables ​​de class de objects (com as quais o comparador calcula a prioridade) podem mudar após a inserção inicial. A maioria das pessoas sugeriu a solução simples de remover o object, atualizando os valores e reinserindo-o novamente, pois é quando o comparador da fila de prioridade é colocado em ação.

Existe uma maneira melhor do que apenas criar uma class wrapper em torno do PriorityQueue para fazer isso?

Você precisa remover e reinserir, pois a fila funciona colocando novos elementos na posição apropriada quando eles são inseridos. Isso é muito mais rápido do que a alternativa de encontrar o elemento de maior prioridade toda vez que você sai da fila. A desvantagem é que você não pode alterar a prioridade após o elemento ter sido inserido. Um TreeMap tem a mesma limitação (assim como um HashMap, que também quebra quando o código hash de seus elementos muda após a inserção).

Se você quiser gravar um wrapper, poderá mover o código de comparação do enfileiramento para o dequeue. Você não precisaria mais ordenar o tempo de enfileiramento (porque o pedido que ele cria não seria confiável de qualquer maneira se você permitir alterações).

Mas isso terá um desempenho pior e você deseja sincronizar na fila se alterar alguma das prioridades. Como você precisa adicionar o código de synchronization ao atualizar prioridades, é melhor apenas desmatar e enfileirar (você precisa da referência à fila nos dois casos).

Eu não sei se existe uma implementação Java, mas se você está alterando muito os valores das chaves, você pode usar um heap Fibonnaci, que tem O (1) custo amortizado para diminuir um valor de chave de uma input no heap, em vez que O (log (n)) como em um heap comum.

Depende muito se você tem controle direto de quando os valores mudam.

Se você sabe quando os valores mudam, você pode remover e reinserir (o que na verdade é bastante caro, já que a remoção requer uma varredura linear sobre a pilha!). Além disso, você pode usar uma estrutura UpdatableHeap (não em estoque java embora) para essa situação. Essencialmente, isso é um heap que rastreia a posição dos elementos em um hashmap. Dessa forma, quando a prioridade de um elemento é alterada, ele pode reparar o heap. Terceiro, você pode procurar por uma pilha de Fibonacci que faça o mesmo.

Dependendo da sua taxa de atualização, uma varredura linear / quicksort / QuickSelect de cada vez também pode funcionar. Em particular, se você tem muito mais atualizações do que pull , este é o caminho a percorrer. QuickSelect é provavelmente melhor se você tiver lotes de atualização e, em seguida, lotes de operações pull.

Para acionar o reheapify, tente isto:

if(!priorityQueue.isEmpty()) { priorityQueue.add(priorityQueue.remove()); }

Algo que eu tentei e funciona até agora, é espreitar para ver se a referência ao object que você está mudando é o mesmo que o header do PriorityQueue, se for, então você poll (), alterar e reinseri-lo ; senão você pode mudar sem polling porque quando a cabeça é pesquisada, então a pilha é de qualquer maneira montada.

DOWNSIDE: Isso altera a prioridade de objects com a mesma prioridade.