Menu

Estrutura de dados da fila de prioridade em C ++ com ilustração

priority queue data structure c with illustration

Experimente Nosso Instrumento Para Eliminar Problemas

Introdução à fila prioritária em C ++ com ilustração.

Priority Queue é uma extensão da fila que discutimos em nosso último tutorial.

É semelhante à fila em certos aspectos, mas difere da fila comum nos seguintes pontos:

  • Cada item na fila de prioridade está associado a uma prioridade.
  • O item com a prioridade mais alta é o primeiro item a ser removido da fila.
  • Se mais de um item tiver a mesma prioridade, seu pedido na fila será considerado.

=> Clique aqui para ver a série de treinamento Absolute C ++.

Fila prioritária em C ++

Podemos visualizar a fila de prioridade como uma versão modificada da fila, exceto que, quando o item deve ser retirado da fila, o item com a prioridade mais alta é recuperado primeiro. Portanto, preferimos usar as filas de prioridade em vez das filas quando precisamos processar os itens com base na prioridade.

O que você aprenderá:

Operações básicas

Vamos discutir algumas das operações básicas suportadas pela fila de prioridade.

  • Inserir (item, prioridade): Insere um item na fila de prioridade com uma determinada prioridade.
  • getHighestPriority (): Retorna um item com a prioridade mais alta.
  • deleteHighestPriority (): Remove um item com a prioridade mais alta.

Além das operações acima, também podemos usar as operações normais de fila como isEmpty (), isFull () e peek ().

Ilustração

Vejamos uma ilustração da fila de prioridade. Para fins de simplicidade, usaremos caracteres ASCII como itens na fila de prioridade. Quanto maior o valor ASCII, maior é a prioridade.

Estado inicial - Priority Queue (PQ) - {} => vazio

ilustração da fila de prioridade

Na ilustração acima, vemos que a operação de inserção é semelhante a uma fila comum. Mas quando chamamos “deleteHighestPriority” para a fila de prioridade, o elemento com a prioridade mais alta é removido primeiro.

Portanto, na primeira vez que chamamos essa função, o item O é removido, enquanto na segunda vez, o item M é removido porque tem prioridade mais alta do que G e A.

Implementação de filas prioritárias em C ++

As filas prioritárias podem ser implementadas usando:

# 1) Arrays / listas vinculadas

Podemos implementar as filas de prioridade usando arrays e esta é a implementação mais simples para as filas de prioridade.

Para representar os itens na fila de prioridade, podemos apenas declarar uma estrutura como abaixo:

struct pq_item{ int item; int priority; };

Declaramos a prioridade também para cada item.

Para inserir um novo item na fila de prioridade, simplesmente temos que inserir o item no final do array.

Para obter o elemento da fila usando getHighestPriority (), precisamos percorrer a matriz desde o início e retornar o item com a prioridade mais alta.

Da mesma forma, para remover o item da fila usando a operação deleteHighestPriority, precisamos percorrer toda a matriz e excluir o item com a prioridade mais alta. Em seguida, mova todos os outros elementos após o item excluído, uma posição para trás.

Também podemos implementar a fila de prioridade usando uma lista vinculada. Podemos realizar todas as operações de maneira semelhante, como arrays. A única diferença é que não precisamos mover os elementos depois de chamar deleteHighestPriority.

# 2) Montes

Usar heaps para implementar uma fila de prioridade é a maneira mais eficiente e oferece um desempenho muito melhor quando comparado às listas e arrays vinculados. Ao contrário da lista e do array vinculados, a implementação do heap leva tempo O (logn) para as operações de inserção e exclusão da fila de prioridade. A operação Get, getHighestPriority leva O (1) tempo.

# 3) Fila de prioridade integrada na biblioteca de modelos padrão (STL) em C ++

Em C ++, temos uma fila prioritária como uma classe adaptativa de contêiner, projetada de forma que o elemento mais alto seja o primeiro elemento da fila e todos os elementos estejam em ordem decrescente.

Portanto, cada item na fila de prioridade tem uma prioridade fixa.

Temos classe em STL, que contém a implementação da fila de prioridade.

As várias operações suportadas pela fila de prioridade são as seguintes:

  1. priority_queue :: size (): Retorna o tamanho da fila.
  2. priority_queue :: empty (): Verifica se a fila está vazia e retorna seu status.
  3. priority_queue :: top (): Retorna uma referência ao elemento mais alto da fila de prioridade.
  4. priority_queue :: push (): Adiciona um item no final da fila de prioridade.
  5. priority_queue :: pop (): Remove o primeiro elemento da fila de prioridade.
  6. priority_queue :: swap (): Usado para trocar o conteúdo de uma fila prioritária por outra do mesmo tipo e tamanho.
  7. tipo de valor de fila de prioridade: O tipo de valor fornece o tipo do elemento armazenado dentro de uma fila de prioridade. Isso também atua como um sinônimo para o parâmetro do modelo.
  8. priority_queue :: emplace (): Usado para inserir um novo elemento no contêiner da fila de prioridade no topo da fila.

No próximo programa, veremos a funcionalidade da fila de prioridade em STL em C ++.

#include #include using namespace std; void displaypq(priority_queue pq) { priority_queue pqueue = pq; while (!pqueue.empty()) { cout << ' ' << pqueue.top(); pqueue.pop(); } cout << ' '; } int main () { priority_queue pq; pq.push(1); pq.push(3); pq.push(5); pq.push(7); pq.push(9); cout << 'Size of the queue(pq.size()): ' << pq.size(); cout << ' Top element of the queue(pq.top()): ' << pq.top(); cout << ' The priority queue pq is : '; displaypq(pq); cout << ' Priority queue, after pq.pop() operation : '; pq.pop(); displaypq(pq); return 0; }

Resultado:

teste de aceitação do usuário (uat)

Tamanho da fila (pq.size ()): 5
Elemento superior da fila (pq.top ()): 9
A fila de prioridade pq é: 9 7 5 3 1
Fila de prioridade, após a operação pq.pop (): 7 5 3 1

Implementação Java para fila prioritária

A fila prioritária em java é uma fila especial onde todos os elementos da fila são ordenados de acordo com a ordem natural ou personalizada usando um comparador fornecido com a fila.

Uma fila de prioridade em Java se parece com a mostrada abaixo:

Implementação Java para fila prioritária

Na fila de prioridade Java, os elementos são organizados de forma que o menor elemento fique na frente da fila e o maior elemento na parte traseira da fila. Portanto, quando removemos o elemento da fila de prioridade, é sempre o menor elemento que é removido.

A classe que implementa a fila de prioridade em Java é “PriorityQueue” e faz parte do framework de coleções de Java. Ele implementa a interface “Queue” do Java.

A seguir está a hierarquia de classes para a classe Java PriorityQueue.

hierarquia de classes para a classe Java PriorityQueue

A seguir, está um exemplo de funcionalidade de fila de prioridade com inteiros como itens em Java.

import java.util.*; class Main { public static void main(String args()) { // Create empty priority queue PriorityQueue priority_Queue = new PriorityQueue(); // Adding items to the priority_Queue using add() priority_Queue.add(1); priority_Queue.add(3); priority_Queue.add(5); priority_Queue.add(7); // display the most priority element System.out.println('peek()::Head value:' + priority_Queue.peek()); // Print all elements in Priotity queue System.out.println('The priority queue:'); Iterator itr = priority_Queue.iterator(); while (itr.hasNext()) System.out.print(itr.next() + ' '); // poll() function to remove the queue elements priority_Queue.poll(); System.out.println(' After poll() function, priority queue:'); Iterator itr2 = priority_Queue.iterator(); while (itr2.hasNext()) System.out.print(itr2.next() + ' '); // remove() function with priority queue priority_Queue.remove(5); System.out.println(' After Remove(5) function, priority queue:'); Iterator itr3 = priority_Queue.iterator(); while (itr3.hasNext()) System.out.print(itr3.next() + ' '); // Check if an element is present using contains() boolean b = priority_Queue.contains(3); System.out.println ( ' Priority queue contains 3?: ' + b); // use toArray() function to get objects from the queue and display the array elements Object() arr = priority_Queue.toArray(); System.out.println ( 'Array elements: '); for (int i = 0; i

Resultado:

peek () :: Valor do cabeçalho: 1
A fila de prioridade:
1 3 5 7
Após a função poll (), fila de prioridade:
3 7 5
Após a função Remover (5), fila de prioridade:
3 7
A fila prioritária contém 3 ?: verdadeiro
Elementos de matriz:
Valor: 3
Valor: 7

No programa acima, usamos a classe PriorityQueue de Java para criar um objeto de PriorityQueue que contém um objeto Integer. Adicionamos elementos à fila usando a função “adicionar”. Em seguida, a função poll () é chamada e exclui o elemento da frente da fila que por acaso é o menor elemento.

Novamente chamamos a função “remove ()” que remove o elemento especificado como um parâmetro da fila. Também usamos a função “Contains ()” para verificar se um determinado elemento está presente na fila. Finalmente, convertemos a fila em um objeto array usando a função “toArray ()”.

Inscrição

  • Balanceamento de carga do sistema operacional e gerenciadores de interrupção: As funções do sistema operacional, como balanceamento de carga e tratamento de interrupções, são implementadas usando filas de prioridade. A atividade de balanceamento de carga agenda os recursos com a prioridade mais alta para transportar com eficácia nosso balanceamento de carga. O tratamento de interrupções é executado atendendo às interrupções com a prioridade mais alta. Essa funcionalidade pode ser implementada com eficácia usando as filas prioritárias.
  • Roteamento: O roteamento é uma função usada para rotear os recursos da rede para que obtenhamos o máximo de rendimento com o mínimo de tempo de resposta. Isso também pode ser implementado usando a fila de prioridade.
  • Emergência Hospitalar: Na emergência de um hospital, os pacientes são atendidos de acordo com a gravidade do estado do paciente. Isso pode ser simulado usando filas de prioridade.
  • Algoritmo de caminho mais curto de Dijkstra: Aqui, o gráfico é armazenado como uma lista de adjacência e podemos usar uma fila de prioridade para extrair a borda ponderada mínima de forma eficiente da lista de adjacência para implementar o algoritmo de caminho mais curto de Dijkstra.
  • A fila de prioridade também pode ser usada para armazenar chaves de nó e extrair o nó de chave mínimo durante a implementação da árvore de abrangência.

Conclusão

As filas prioritárias nada mais são do que a extensão da fila. Mas, ao contrário das filas que adicionam / removem itens usando a abordagem FIFO, na fila de prioridade os itens são removidos da fila de acordo com a prioridade. Assim, cada item na fila está associado a uma prioridade e o item com a maior prioridade é o primeiro a ser retirado da fila.

A fila de prioridade tem três operações principais, ou seja, insert (), getHighestPriority () e deleteHighestPriority (). A fila de prioridade pode ser implementada usando matrizes ou lista vinculada, mas o funcionamento não é muito eficiente. A fila de prioridade também pode ser implementada usando heaps e o desempenho é muito mais rápido.

Em C ++, também temos uma classe de contêiner que implementa a funcionalidade de uma fila de prioridade. Em Java, há uma classe integrada priority_queue que fornece a funcionalidade de uma fila prioritária.

A fila de prioridade é usada principalmente em aplicativos que exigem que os itens sejam processados ​​de acordo com a prioridade. Por exemplo, ele é usado no tratamento de interrupções.

Nosso próximo tutorial irá explorar tudo sobre a fila circular, que é outra extensão da fila.

=> Visite aqui para obter o curso C ++ completo com especialistas.

Leitura recomendada

^