Como usar heapq no Python?

[

O módulo heapq do Python: Usando Heaps e Filas de Prioridade

Os heaps e as filas de prioridade são estruturas de dados pouco conhecidas, mas surpreendentemente úteis. Para muitos problemas que envolvem encontrar o melhor elemento em um conjunto de dados, eles oferecem uma solução fácil de usar e altamente eficaz. O módulo heapq do Python faz parte da biblioteca padrão. Ele implementa todas as operações de heap em um nível de baixo nível, bem como alguns usos comuns de alto nível para heaps.

Neste tutorial, você aprenderá:

• O que são heaps e filas de prioridade e como eles se relacionam entre si
• Que tipos de problemas podem ser resolvidos usando um heap
• Como usar o módulo heapq do Python para resolver esses problemas

Este tutorial é para Pythonistas que estão familiarizados com listas, dicionários, conjuntos e geradores e estão procurando por estruturas de dados mais sofisticadas.

Você pode acompanhar os exemplos neste tutorial baixando o código-fonte no link abaixo:

O que são Heaps?

Heaps são comumente usados para implementar filas de prioridade. Eles são a estrutura de dados concreta mais popular para implementar a estrutura de dados abstrata de fila de prioridade.

Estruturas de dados concretas também especificam garantias de desempenho. As garantias de desempenho definem a relação entre o tamanho da estrutura e o tempo que as operações levam. Compreender essas garantias permite prever quanto tempo o programa levará conforme o tamanho de suas entradas muda.

Estruturas de Dados, Heaps e Filas de Prioridade

Estruturas de dados abstratas especificam operações e as relações entre elas. A estrutura de dados abstrata de fila de prioridade, por exemplo, suporta três operações:

1. is_empty verifica se a fila está vazia.
2. add_element adiciona um elemento à fila.
3. pop_element remove o elemento com a maior prioridade.

Filas de prioridade são comumente usadas para otimizar a execução de tarefas, onde o objetivo é trabalhar na tarefa com a maior prioridade. Após a conclusão de uma tarefa, sua prioridade é reduzida e ela é retornada à fila.

Existem duas convenções diferentes para determinar a prioridade de um elemento:

1. O elemento maior tem alta prioridade.
2. O elemento menor tem alta prioridade.

No módulo heapq do Python, a primeira convenção é adotada. Isso significa que um heap armazena elementos em uma lista em que o elemento de maior prioridade está sempre na posição 0.

Agora que você entende o básico das estruturas de dados de heaps e filas de prioridade, vamos ver como utilizar o módulo heapq do Python para realizar operações básicas em heaps e resolver problemas específicos.