A complexidade do tempo de estourar (remover o elemento com a maior prioridade) de uma fila de prioridade depende da implementação subjacente da fila de prioridade. Aqui está um colapso de implementações comuns:

* heap binário:
* o (log n) . Esta é a implementação mais comum e eficiente. A remoção da raiz (elemento de prioridade mais alta) toma O (1). No entanto, você precisa substituir a raiz pelo último elemento na pilha e "Heapify Down" para restaurar a propriedade Heap. Esta operação Heapify leva o tempo O (log n), onde n é o número de elementos na pilha.

* Árvore de pesquisa binária (BST):
* o (log n) No caso médio de um BST equilibrado (como uma árvore AVL ou uma árvore preta-preta). Encontrar o máximo (ou o mínimo, dependendo da prioridade) é O (log n) e removê -lo também é O (log n).
* o (n) Na pior das hipóteses, para um BST desequilibrado. Se a árvore estiver distorcida (por exemplo, lembrar uma lista vinculada), encontrar e remover o máximo/mínimo pode levar tempo linear.

* Array ou lista vinculada (não ordenada):
* o (n) . Você precisa iterar em toda a lista para encontrar o elemento com a maior prioridade e removê -la.

* Array ou lista vinculada (ordenada):
* Se ordenado por prioridade (por exemplo, matriz classificada):o elemento com maior prioridade (provavelmente no final ou no início, dependendo da ordem) pode ser O (1). No entanto, se você estiver usando uma matriz classificada e precisar manter a ordem classificada após a remoção do elemento, pode ser necessário mudar elementos, resultando em O (n) no pior caso. As listas vinculadas podem evitar a mudança, portanto, o surto é O (1) se você souber onde está o elemento de prioridade mais alta, mas achando que ainda era o (n) para começar.

* fibonacci heap:
* o (log n) tempo amortizado. Os montes de Fibonacci são mais complexos de implementar, mas eles oferecem desempenho teoricamente melhor para determinadas operações, principalmente quando você tem muitas operações de `` diminuição-chave '. "Amortizado" significa que, embora as operações individuais possam levar mais tempo, a complexidade média do tempo em relação a uma sequência de operações é O (log n).

Resumo:

| Implementação | Complexidade do tempo (Popping) |
| ----------------------- | ------------------------- |
| Heap binário | O (log n) |
| BST equilibrado | O (log n) |
| BST desequilibrado | O (n) |
| Array/lista não ordenada | O (n) |
| Matriz/lista ordenada | O (1) ou O (n) |
| Heap fibonacci | O (log n) (amortizado) |

Na prática:

A implementação mais comum para filas de prioridade é o heap binário , devido ao seu bom desempenho (O (log n)) e implementação relativamente simples. Portanto, geralmente você pode assumir a complexidade do tempo de aparecer de uma fila de prioridade para ser o (log n) A menos que a documentação ou contexto especifique explicitamente uma estrutura de dados subjacente diferente.