A complexidade do tempo das operações comuns em um `priorityQueue` em Java depende da operação específica. Aqui está um colapso:
*
`add (e e)` / `oferta (e e)` (inserção): O (log n) - Isso ocorre porque a fila de prioridade precisa manter sua propriedade Heap, que requer peneirar o novo elemento para cima ou para baixo na pilha.
*
`remover ()` / `poll ()` (remoção do elemento de prioridade mais alta): O (log n) - A remoção do elemento raiz (maior prioridade) requer substituí -lo pelo último elemento e, em seguida, peneirando o elemento de substituição na pilha para restaurar a propriedade Heap.
*
`peek ()` (acessando o elemento de prioridade mais alta): O (1) - Espreitar o elemento de prioridade mais alta (a raiz da pilha) é uma operação de acesso direto.
*
`contém (objeto o)`: O (n) - Isso requer iterando através dos elementos da fila para verificar a igualdade. O PriorityQueues em Java não fornece uma maneira eficiente de verificar a contenção.
*
`remover (objeto o)`: O (n) - semelhante a `contém ()`, isso envolve iterando os elementos para encontrar e remover o objeto especificado. Depois de remover o objeto, a propriedade Heap deve ser mantida, que, na pior das hipóteses, pode levar o tempo O (n). (Remover um elemento arbitrário não é uma operação de fila de prioridade padrão, e o desempenho reflete isso.)
*
`size ()`: O (1) - O tamanho é mantido como uma variável de membro, portanto, acessar é uma operação de tempo constante.
*
`isEmpty ()`: O (1) - basta verificar se o tamanho é 0.
*
`clear ()`: O (n) - remove todos os elementos da fila. Embora a remoção de elementos individuais possa levar O (log n), a limpeza de toda a fila toma O (n). Em algumas implementações, isso pode ser implementado como O (1), apenas redefinindo a matriz e o tamanho internos.
*
`iterator ()`: O (1) - retorna um iterador para a fila de prioridade. O próprio iterador * não é * ordenado, e a iteração dos elementos será O (n).
Considerações importantes: *
`priorityqueue` é implementado como uma pilha binária. A estrutura de dados da heap é o que lhe dá seu desempenho logarítmico para inserção e remoção do elemento de prioridade mais alta.
*
O comparador é crucial. O comparador (ou a ordem natural dos elementos se nenhum comparador for fornecido) é o que determina a prioridade dos elementos. O método `Compare ()` do comparador deve ser eficiente (normalmente O (1)) para as operações gerais da fila de prioridade para manter sua complexidade declarada.
*
remover elementos arbitrários (`remover (objeto o)`) é ineficiente. Se você frequentemente precisar remover elementos arbitrários de uma fila de prioridade, considere o uso de uma estrutura de dados diferente ou uma combinação de estruturas de dados (por exemplo, um `Treeeset` combinado com um` hashmap` para rastrear as posições do elemento). As filas de prioridade padrão são otimizadas para acesso eficiente ao elemento de prioridade mais alta.
em resumo: As operações principais de `add ()` e `remover ()` (do * elemento prioritário * mais alto * são O (log n), tornando o `priorityqueue` uma opção muito eficiente para cenários em que você precisa manter uma coleção classificada e acessar repetidamente ou remover o elemento mínimo (ou máximo, dependendo do comparador).
