Como usar o C ++ Priority_queue?

Em C ++, uma fila é uma estrutura de dados da lista em que o primeiro elemento a ser colocado na lista é o primeiro elemento a ser removido, quando a remoção será realizada. Uma fila de prioridade em C ++ é semelhante, mas tem algumas pedidos; É o elemento com o maior valor que é removido primeiro. A fila de prioridade ainda pode ser configurada para que seja o elemento com o menor valor que é removido primeiro. Qualquer fila deve ter pelo menos o empurrar() função e o pop () função. O empurrar() função adiciona um novo elemento na parte traseira. Para a fila normal, o pop () A função remove o primeiro elemento já empurrado. Para a fila de prioridade, o pop () A função remove o elemento com a maior prioridade, que pode ser a maior ou menor, dependendo do esquema de pedidos.

Para usar o C ++ Priority_queue, o programa deve começar com o código como:

#incluir
#incluir
usando namespace std;

Inclui a biblioteca da fila no programa.

Para continuar lendo, o leitor deveria ter um conhecimento básico de C++.

Conteúdo do artigo

• Construção Básica
• Funções de membros importantes
• Outras funções da fila de prioridade
• Dados da string
• Outras construções de fila de prioridade
• Conclusão

Construção Básica

A estrutura de dados deve ser construída primeiro antes de poder ser usada. Construção aqui significa instantar um objeto da classe de fila da biblioteca. O objeto da fila deve então ter um nome dado a ele pelo programador. A sintaxe mais simples para criar uma fila de prioridade é:

Fila de prioridade Queuename;

Com esta sintaxe, o maior valor é removido primeiro. Um exemplo da instanciação é:

Fila de prioridade pq;

ou

Fila de prioridade pq;

O vetor e o deque são duas estruturas de dados em c++. Um priority_queue pode ser criado com qualquer um deles. A sintaxe para criar uma fila de prioridade a partir da estrutura vetorial é:

Fila de prioridade, Compare> pq;

Um exemplo dessa instanciação é:

Fila de prioridade, menos > pq;

Observe a lacuna entre> e> no final da declaração. Isso é para evitar confusão com >>. O código de comparação padrão é "menos", o que significa o melhor, e não necessariamente o primeiro valor, seria removido primeiro. Portanto, a declaração de criação pode ser simplesmente escrita como:

Fila de prioridade > pq;

Se o menor valor for removido primeiro, a declaração deve ser:

Fila de prioridade, maior > pq;

Funções de membros importantes

A função push ()
Esta função empurra um valor, que é o seu argumento, para o priority_queue. Ele retorna vazio. O código a seguir ilustra o seguinte:

Fila de prioridade pq;
pq.push (10);
pq.push (30);
pq.push (20);
pq.push (50);
pq.push (40);

Esta prioridade_queue recebeu 5 valores inteiros na ordem de 10, 30, 20, 50, 40. Se todos esses elementos forem saídos da fila de prioridade, eles sairão na ordem de 50, 40, 30, 20, 20, 10.

A função pop ()
Esta função remove do priority_queue o valor com a maior prioridade. Se o código de comparação for "maior", ele removerá o elemento com o menor valor. Se chamado novamente, ele remove o próximo elemento com o menor valor do restante; chamado novamente, ele remove o próximo menor valor presente e assim por diante. Ele retorna vazio. O código a seguir ilustra o seguinte:

Fila de prioridade, maior > pq;
pq.push ('a');
pq.push ('c');
pq.push ('b');
pq.push ('e');
pq.push ('d');

Observe que, para chamar uma função de membro, o nome do objeto deve ser seguido por um ponto e depois a função.

A função top ()
O pop () A função remove o próximo valor da maior prioridade, mas não a devolve, como pop () é uma função vazia. Use o principal() função para saber o valor da maior prioridade que deve ser removida a seguir. O principal() Função retorna uma cópia do valor da maior prioridade na prioridade_queue. O código a seguir, onde o próximo valor da maior prioridade é o menor valor, ilustra este

Fila de prioridade, maior > pq;
pq.push ('a'); pq.push ('c'); pq.push ('b'); pq.push ('e'); pq.push ('d');
char ch1 = pq.principal(); pq.pop ();
CHAR CH2 = PQ.principal(); pq.pop ();
char ch3 = pq.principal(); pq.pop ();
char ch4 = pq.principal(); pq.pop ();
char ch5 = pq.principal(); pq.pop ();
cout<

A saída é 'a "b" c "d" e'.

A função vazia ()
Se um programador usa o principal() Função em uma prioridade vazia_queue, após a compilação bem -sucedida, ele receberia uma mensagem de erro como:

falha de segmentação (despejo de núcleo)

Portanto, sempre verifique se a fila de prioridade não está vazia antes de usar o principal() função. O vazio() A função de membro retorna um bool, verdadeiro, se a fila estiver vazia e falsa se a fila não estiver vazia. O código a seguir ilustra o seguinte:

Fila de prioridade pq;
int i1 = 10; int i2 = 30; int i3 = 20; int i4 = 50; int i5 = 40;
pq.push (i1); pq.push (i2); pq.push (i3); pq.push (i4); pq.push (i5);
enquanto(!pq.vazio())

cout << pq.top() << ";
pq.pop ();

cout << '\n';

Outras funções da fila de prioridade

A função size ()
Esta função retorna a duração da fila de prioridade, como ilustra o código a seguir:

Fila de prioridade pq;
int i1 = 10; int i2 = 30; int i3 = 20; int i4 = 50; int i5 = 40;
pq.push (i1); pq.push (i2); pq.push (i3); pq.push (i4); pq.push (i5);
int len ​​= pq.tamanho();
cout << len << '\n';

A saída é 5.

A função swap ()
Se dois Priority_queues forem do mesmo tipo e tamanho, eles podem ser trocados por essa função, como o código a seguir mostra:

Fila de prioridade PQ1;
int i1 = 10; int i2 = 30; int i3 = 20; int i4 = 50; int i5 = 40;
PQ1.push (i1); PQ1.push (i2); PQ1.push (i3); PQ1.push (i4); PQ1.push (i5);
Fila de prioridade PQA;
int it1 = 1; int it2 = 3; int it3 = 2; int it4 = 5; int it5 = 4;
PQA.push (it1); PQA.push (it2); PQA.push (it3); PQA.push (it4); PQA.push (it5);
PQ1.troca (PQA);
enquanto(!PQ1.vazio())

cout << pq1.top() << ";
PQ1.pop ();
cout<<'\n';
enquanto(!PQA.vazio())

cout << pqA.top() << ";
PQA.pop ();
cout<<'\n';

A saída é:

5 4 3 2 1
50 40 30 20 10

O emplace () fucção
O emplace () A função é semelhante à função push. O código a seguir ilustra o seguinte:

Fila de prioridade PQ1;
int i1 = 10; int i2 = 30; int i3 = 20; int i4 = 50; int i5 = 40;
PQ1.emplace (i1);
PQ1.emplace (i2);
PQ1.emplace (i3);
PQ1.emplace (i4);
PQ1.emplace (i5);
enquanto(!PQ1.vazio())

cout << pq1.top() << ";
PQ1.pop ();
cout<<'\n';

A saída é:

50 40 30 20 10

Dados da string

Ao comparar strings, a classe String deve ser usada e não o uso direto dos literais de cordas porque compararia ponteiros e não as cordas reais. O código a seguir mostra como a classe String é usada:

#incluir
Fila de prioridade PQ1;
String S1 = String ("Pen"),
s2 = string ("lápis"),
s3 = string ("Livro de exercícios"),
s4 = string ("Livro de texto"),
s5 = string ("régua");
PQ1.push (s1);
PQ1.push (s2);
PQ1.push (S3);
PQ1.push (s4);
PQ1.push (S5);
enquanto(!PQ1.vazio())

cout << pq1.top() << " ";
PQ1.pop ();
cout<<'\n';

A saída é:

Livro do livro de texto Livro de exercícios de caneta lápis

Outras construções de fila de prioridade

Criação explícita de um vetor
Uma fila de prioridade pode ser criada explicitamente a partir de um vetor, como mostra o código a seguir:

#incluir
vetor vtr = 10, 30, 20, 50, 40;
Fila de prioridade PQ (Vtr.BEGIN (), VTR.fim());
enquanto(!pq.vazio())

cout << pq.top() << ";
pq.pop ();
cout<<'\n';

A saída é: 50 40 30 20 10. Desta vez, o cabeçalho do vetor também deve ser incluído. Os argumentos para a função do construtor levam os ponteiros iniciantes e finais do vetor. O tipo de dados para o vetor e o tipo de dados para o priority_queue devem ser os mesmos.

Para obter o menor valor a prioridade, a declaração para o construtor seria:

Fila de prioridade, maior> int >> PQ (VTR.BEGIN (), VTR.fim());

Criação explícita de uma matriz
Uma fila de prioridade pode ser criada explicitamente a partir de uma matriz, pois o código a seguir mostra:

int arr [] = 10, 30, 20, 50, 40;
Fila de prioridade PQ (arr, arr+5);
enquanto(!pq.vazio())

cout << pq.top() << ";
pq.pop ();
cout<<'\n';

A saída é: 50 40 30 20 10. Os argumentos para a função do construtor levam os ponteiros iniciantes e finais da matriz. ARR retorna o ponteiro inicial: “arr+5” retorna o ponteiro logo após a matriz e 5 é o tamanho da matriz. O tipo de dados para a matriz e o tipo de dados para o priority_queue deve ser o mesmo.

Para obter o menor valor a prioridade, a declaração para o construtor seria:

Fila de prioridade, maior > pq (arr, arr+5);

Nota: em C ++, o priority_queue é realmente chamado de adaptador, não apenas um contêiner.

Código de comparação personalizado

Ter todos os valores na fila de prioridade ascendente ou toda a descendência não é a única opção para a fila de prioridade. Por exemplo, uma lista de 11 números inteiros para uma pilha máxima é:

88, 86, 87, 84, 82, 79,74, 80, 81 ,, 64, 69

O valor mais alto é 88. Isto é seguido por dois números: 86 e 87, que são inferiores a 88. O restante dos números é menor que esses três números, mas não realmente em ordem. Existem duas células vazias na lista. Os números 84 e 82 são inferiores a 86. Os números 79 e 74 são inferiores a 87. Os números 80 e 81 são inferiores a 84. Os números 64 e 69 são inferiores a 79.

A colocação dos números segue os critérios max -heap - veja mais tarde. Para fornecer esse esquema para o priority_queue, o programador deve fornecer seu próprio código de comparação - veja mais adiante.

Conclusão

Um C ++ Priority_queue é uma primeira fila. A função do membro, empurrar(), adiciona um novo valor à fila. A função do membro, principal(), lê o valor máximo na fila. A função do membro, pop (), remove sem retornar o valor superior da fila. A função do membro, vazio(), verifica se a fila está vazia. No entanto, o priority_queue difere da fila, nisso, segue algum algoritmo de prioridade. Pode ser maior, do primeiro ao último, ou menos, do primeiro ao último. Os critérios (algoritmo) também podem ser definidos pelo programador.