Uma fila de prioridade é um tipo abstrato de dado (ADT) que funciona de maneira semelhante a uma fila ou pilha, mas com uma diferença fundamental. Como você já deve saber, filas padrão seguem uma abordagem FIFO (First-in, First-out), onde o primeiro elemento adicionado à fila é o primeiro a ser removido da fila. Pilhas seguem uma abordagem LIFO (Last-in, First-out), onde o último elemento adicionado à pilha é o primeiro a ser removido da pilha. Filas e pilhas consideram apenas a ordem de inserção dos elementos. No entanto, filas de prioridade levam em conta a "prioridade" dos elementos. A prioridade é usada para determinar qual elemento deve ser removido em seguida. Normalmente, o elemento com a maior prioridade é removido primeiro, mas algumas implementações também podem escolher remover o elemento com a menor prioridade primeiro. Isso dependerá dos requisitos do seu programa. Filas de prioridade são muito úteis para aplicações práticas como encontrar o caminho mais curto entre dois locais, agendar tarefas em sistemas operacionais, simular tráfego, comprimir dados e gerenciar redes. Na prática, filas de prioridade são comumente implementadas usando uma estrutura de dados heap. Uma heap é uma estrutura de dados em árvore com uma propriedade muito específica chamada heap property. Essa propriedade determina a relação entre cada nó e seus filhos, com base no tipo de heap. Existem dois tipos principais de heaps: * Heap máximo * Min-heap Em uma max-heap, o valor de cada nó é maior ou igual ao valor de seus filhos. Neste exemplo, você pode ver uma estrutura de árvore com os nós 8, 7, 5, 2 e 1. Note que o nó 7 é maior que o nó 2 e o nó 1, seguindo a propriedade heap. Isso é verdade para todos os outros nós também. <img src="https://cdn.G.E.A.R ACADEMY.org/curriculum/lecture-transcripts/how-do-priority-queues-and-heaps-work-1.png" alt="A max-heap tree structure showing nodes with values 8 at the root, 7 and 5 as children of 8, and 2 and 1 as children of 7, demonstrating that each parent node is greater than its children."> Em contraste, em uma min-heap, o valor de cada nó é menor ou igual ao valor de seus filhos. Neste exemplo, temos nós com valores 4, 7, 9, 12 e 15. Por exemplo, o nó 7 é menor que o nó 12 e o nó 15, seguindo a propriedade do heap. Isso também é verdade para todos os outros nós. <img src="https://cdn.G.E.A.R ACADEMY.org/curriculum/lecture-transcripts/how-do-priority-queues-and-heaps-work-2.png" alt="A min-heap tree structure showing nodes with values 4 at the root, 7 and 9 as children of 4, and 12 and 15 as children of 7, demonstrating that each parent node is less than its children."> A propriedade heap é fundamental porque garante que o elemento máximo (ou mínimo) (dependendo do tipo de heap) esteja sempre no topo, o que facilita muito a remoção. Na prática, heaps são tipicamente implementados como arrays para acessar nós pai e filhos de forma eficiente. Usar arrays simplifica a lógica para acessar esses valores ou "nós" porque nos bastidores, se o heap mantém a estrutura de uma árvore binária completa, a implementação em array requer apenas operações matemáticas simples baseadas em seus índices para encontrar onde os elementos estão localizados na memória. Python possui um módulo embutido heapq que você pode usar para trabalhar com uma implementação de min-heap. Funciona operando diretamente em listas Python, seguindo etapas específicas que trabalham com os elementos como se a lista fosse um heap, preservando a propriedade do heap. Para usar este módulo, você só precisa importá-lo:

import heapq

Então, você precisa definir uma lista vazia. Esta será a estrutura de dados subjacente para o heap:

my_heap = []

Para adicionar elementos ao heap, você deve chamar heappush(), passando o nome do heap e o elemento que deseja adicionar como argumentos. Isso adicionará automaticamente o elemento à lista onde ele deve estar, para preservar a propriedade do heap:

heapq.heappush(my_heap, 9)

Para obter o elemento com a maior prioridade (neste caso, o menor valor), você faria uma chamada a heappop():

heapq.heappop(my_heap)

heappushpop() combina ambas as operações em uma única chamada. Isto é mais eficiente do que chamá-los em sequência separadamente, especialmente quando o heap é grande, pois ele realiza apenas uma operação de "heapify" para reordenar a lista como um heap:

heapq.heappushpop(my_heap, 15)

Se você já tem uma lista e quer transformá-la em um heap, você pode chamar heapify(), passando a lista como argumento:

heapq.heapify(my_heap)

Mas atualmente, estamos ordenando os elementos pelos seus valores, certo? E se quisermos ordená-los pela sua "prioridade" em vez disso? Você pode fazer isso armazenando tuplas com esta estrutura: (priority, element). Como as tuplas são comparadas elemento por elemento da esquerda para a direita, as prioridades serão comparadas primeiro e as decisões serão tomadas com base nelas. Observe que, neste caso, valores menores representarão prioridades maiores. Isso significa que uma tupla com prioridade 1 terá uma prioridade maior do que uma tupla com prioridade 3:

my_heap = []

heapq.heappush(my_heap, (3, "A"))
heapq.heappush(my_heap, (2, "B"))
heapq.heappush(my_heap, (1, "C"))

Se você precisar que elementos com a mesma prioridade sejam removidos na ordem em que foram inseridos, pode considerar incluir um contador único como o segundo elemento da sua tupla para desempatar, assim: (priority, counter, element). Agora vamos falar sobre a eficiência dos heaps. As complexidades de tempo média e no pior caso para inserir e extrair o valor mínimo ou máximo de uma heap (dependendo do tipo de heap) são logarítmicas, O(log n), porque o número de trocas necessárias geralmente é proporcional à altura da heap, que é log(n). A complexidade de tempo média e no pior caso para a operação "peek" é tempo constante, O(1). O peek envolve obter o valor mínimo ou máximo (dependendo do tipo de heap) sem removê-lo. A operação "heapify", onde o heap é construído a partir de uma lista não ordenada, tem complexidade de tempo linear, O(n), nos casos médio e pior. De forma semelhante, tanto a busca quanto a exclusão de um elemento arbitrário têm complexidades médias e piores casos lineares de tempo O(n), pois potencialmente exigem percorrer todo o heap. E quanto espaço eles requerem? A complexidade de espaço do heap é linear, O(n), onde n é o número de elementos que ele contém. Ele só precisa armazenar os elementos e uma pequena sobrecarga adicional para o próprio objeto da lista. Filas de prioridade e heaps são muito importantes em ciência da computação. Eles permitem que você encontre e use rapidamente os elementos mais importantes de uma lista. Essa eficiência é crucial para muitos programas de computador que executam tarefas críticas do mundo real, como encontrar a rota mais rápida em um mapa.