sexta-feira, 10 de outubro de 2014

[Python] - Implementando uma fila de prioridades

Olá pessoal, nesse post nós iremos implementar uma fila de prioridades utilizando a linguagem de programação Python.

Fila de prioridades, como o próprio nome já indica, é uma estrutura de dados (uma fila) que mantém uma coleção de elementos, cada um com uma prioridade associada.

Cada elemento dessa fila possui uma prioridade. Para exemplificar, nós iremos construir uma classe chamada Pessoa, onde cada objeto dessa classe irá ter um nome e uma idade. A prioridade será a idade da pessoa.

Para você não esquecer sobre fila de prioridades, basta lembrar de uma fila de banco onde tem-se um esquema de prioridade em que clientes preferenciais, idosos enfim, possuem uma prioridade mais alta de atendimento.

Além da classe Pessoa, teremos uma classe para representar a nossa fila de prioridades. Iremos utilizar também o módulo "heapq" que contém funções para nos auxiliar na implementação.

Veja o código abaixo e logo em seguida a explicação:


Linha 3: importação do módulo "heapq" que irá nos auxiliar na implementação da fila de prioridades.

Linha 5: classe FilaDePrioridade.

Linha 8: criação da fila (uma lista) inicialmente vazia.

Linha 9: criação do "indice" cujo valor inicialmente é 0. Explicarei mais adiante o porquê dessa variável.

Linha 11: função para inserir elementos na fila. É passado o item que vai ser inserido e a prioridade que no nosso caso será a idade da pessoa.

Linha 12: a função "heappush" insere itens na lista _fila. A fila é formada por tuplas. O valor de "prioridade" é negado para que a fila seja ordenada dos itens de mais alta prioridade para a mais baixa prioridade, ou seja, pessoas mais velhas terão prioridade sobre pessoas mais novas. A ordem normal de uma heap é ordenar do menor para o maior, por isso a prioridade foi negada. O "indice" tem como finalidade ordenar os itens com o mesmo nível de prioridade. Como nós incrementamos essa variável constantemente, os itens serão ordenados de acordo com a ordem em que foram inseridos. O "indice" também tem o papel de fazer com que as operações de comparação funcionem corretamente.

Linha 13: a variável "indice" é incrementada.

Linha 15: função para remover elementos da fila.

Linha 16: retorna o elemento removido utilizando a função "heappop" que remove itens da lista _fila. Já falei anteriormente que a fila é formada por tuplas no formato (-prioridade, indice, item). Bem, a função "remover" retorna essa tupla, é colocado o [-1] para pegar o último elemento da tupla, ou seja, o item que nada mais é que a pessoa que foi removida.

Linha 19: classe Pessoa.

Linha 20: é passado o nome desse pessoa.

Linha 21: é atribuído um nome à pessoa.

Linha 23: o método "__repr__" faz com que um objeto seja impresso de maneira legível. Nesse caso coloquei para retornar o nome da pessoa. Se eu não fizesse isso, iria imprimir o objeto numa representação difícil de entender. Retornando o nome, então irá imprimir o nome da pessoa sempre que eu quiser mostrar o objeto.

Linha 27: criação de uma fila.

Linhas 28 à 31: inserção de itens na fila.

Linha 33: utiliza a função "remover" para remover um item da fila. Qual será a saída? A prioridade é do maior valor para o menor, ou seja, de pessoas mais velhas para mais novas. A pessoa mais velha é o Felipe, portanto será impresso o nome "Felipe".

A complexidade das operações de inserção e remoção é de O(logN) onde N é o número de itens da heap.

O código foi testado nas versões do Python 2.7 e 3.4. Quaisquer dúvidas deixem nos comentários, até a próxima.


Nenhum comentário: