Explorando a STL - Aula 7 - Priority_Queue

Escrito por Lúcio Figueiredo e Anita Almeida

A Priority_Queue (ou Fila de Prioridade) é uma estrutura de dados bastante útil da STL do C++, e possui muitas semelhanças com a queue. Estra estrutura é armazena uma fila de elementos de tal forma que o elemento na mais à frente é sempre o de maior valor.

Declaração

Para declarar uma fila de prioridade, é necessário usar a biblioteca queue. Depois disso, basta especificar o tipo dos elementos que serão armazenados na fila e o seu nome, da seguinte forma:

Inserção de elementos

A sintaxe para inserir um elemento na priority_queue é a mesma da queue - basta utilizar o comando push(), como indicado no código abaixo:

Acessar o maior elemento

Como já dito, o elemento de maior valor presente na estrutura é sempre o elemento na frente da fila. Para encontrar o maior elemento, basta usar o comando top().

Remoção de um elemento

Para remover um elemento da frente da fila, o comando pop() é utilizado, da mesma forma que na queue. Lembre-se que, diferentemente da queue, o elemento no topo da fila é sempre o elemento de maior valor presente nela.

Ordenação da fila de maneira crescente

É possível fazer uma alteração na fila para que o elemento do topo seja sempre o menor. Para isso, basta modificar a declaração da priority_queue da seguinte forma:

Complexidade das operações

Todas as operações realizadas na Priority_Queue possuem complexidade O(\log_{} N), onde N é o total de elementos na fila, assim como na estrutura de dados set.

Problemas para praticar

Problema 1 - Telemarketing