Para usar o C ++ priority_queue, o programa deve começar com código como:
#incluir
#incluir
usando namespacehoras;
Inclui a biblioteca de filas no programa.
Para continuar lendo, o leitor deve ter um conhecimento básico de C ++.
Conteúdo do Artigo
- Construção Básica
- Funções de membro importantes
- Outras funções de fila de prioridade
- String Data
- Outras construções de fila de prioridade
- Conclusão
Construção Básica
A estrutura de dados deve ser construída antes de poder ser usada. Construção aqui significa instanciar um objeto da classe de fila da biblioteca. O objeto de fila deve então ter um nome fornecido a ele pelo programador. A sintaxe mais simples para criar uma fila de prioridade é:
Fila de prioridade<modelo>queueName;
Com essa sintaxe, o maior valor é removido primeiro. Um exemplo de instanciação é:
Fila de prioridade<int>pq;ou
Fila de prioridade<Caracteres>pq;
O vetor e o deque são duas estruturas de dados em C ++. Uma priority_queue pode ser criada com qualquer um deles. A sintaxe para criar uma fila de prioridade a partir da estrutura vetorial é:
Fila de prioridade<tipo, vetor<mesmo tipo>, comparar>pq;Um exemplo dessa instanciação é:
Fila de prioridade<int, vetor<int>, menos<int> >pq;Observe a lacuna entre> e> no final da declaração. Isso evita confusão com >>. O código de comparação padrão é menor, o que significa que o maior, 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<int, vetor<int> >pq;Se o menor valor deve ser removido primeiro, a instrução deve ser:
Fila de prioridade<int, vetor<int>, maior<int> >pq;Funções de membro importantes
A função push ()
Esta função envia um valor, que é seu argumento, para a priority_queue. Ele retorna vazio. O código a seguir ilustra isso:
pq.Empurre(10);
pq.Empurre(30);
pq.Empurre(vinte);
pq.Empurre(cinquenta);
pq.Empurre(40);
Este priority_queue recebeu 5 valores inteiros na ordem de 10, 30, 20, 50, 40. Se todos esses elementos forem retirados da fila de prioridade, eles sairão na ordem de 50, 40, 30, 20, 10.
A função pop ()
Esta função remove da priority_queue o valor com a prioridade mais alta. 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 resto; chamado novamente, ele remove o próximo menor valor presente e assim por diante. Ele retorna vazio. O código a seguir ilustra isso:
pq.Empurre('para');pq.Empurre('c');pq.Empurre('b');pq.Empurre('E');pq.Empurre('d');
Observe que, para chamar uma função de membro, o nome do objeto deve ser seguido por um ponto e, em seguida, pela função.
A função top ()
o pop () função remove o próximo valor de maior prioridade, mas não o retorna, pois pop () é uma função vazia. Use o principal() função para saber o valor de maior prioridade que deve ser removido em seguida. o principal() função retorna uma cópia do valor de maior prioridade na priority_queue. O código a seguir, onde o próximo valor de maior prioridade é o menor valor, ilustra isso
pq.Empurre('para');pq.Empurre('c');pq.Empurre('b');pq.Empurre('E');pq.Empurre('d');
Caracteresch1=pq.principal();pq.pop();
Caracteresch2=pq.principal();pq.pop();
Caracteresch3=pq.principal();pq.pop();
Caracteresch4=pq.principal();pq.pop();
Caracteresch5=pq.principal();pq.pop();
custo<<ch1<<''<<ch2<<''<<ch3<<''<<ch4<<''<<ch5<<' n';
A saída é ‘a’ ‘b’ ‘c’ ‘d’ ‘e’.
A função empty ()
Se um programador usa o principal() em uma priority_queue vazia, após a compilação bem-sucedida, ele receberia uma mensagem de erro como:
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 falso, se a fila não estiver vazia. O código a seguir ilustra isso:
Fila de prioridade<int>pq;inti1= 10; inti2= 30; inti3= vinte; inti4= cinquenta; inti5= 40;
pq.Empurre(i1);pq.Empurre(i2);pq.Empurre(i3);pq.Empurre(i4);pq.Empurre(i5);
enquanto(!pq.vazio())
{
custo <<pq.principal() << '';
pq.pop();
}
custo << ' n';
Outras funções de fila de prioridade
A função size ()
Esta função retorna o comprimento da fila de prioridade, conforme o código a seguir ilustra:
inti1= 10; inti2= 30; inti3= vinte; inti4= cinquenta; inti5= 40;
pq.Empurre(i1);pq.Empurre(i2);pq.Empurre(i3);pq.Empurre(i4);pq.Empurre(i5);
intlen=pq.Tamanho();
custo <<len<< ' n';
A saída é 5.
A função swap ()
Se duas priority_queues forem do mesmo tipo e tamanho, elas podem ser trocadas por esta função, como mostra o código a seguir:
inti1= 10; inti2= 30; inti3= vinte; inti4= cinquenta; inti5= 40;
pq1.Empurre(i1);pq1.Empurre(i2);pq1.Empurre(i3);pq1.Empurre(i4);pq1.Empurre(i5);
Fila de prioridade<int>pqA;
intit1= 1; intit2= 3; intit3= 2; intit4= 5; intit5= 4;
pqA.Empurre(it1);pqA.Empurre(it2);pqA.Empurre(it3);pqA.Empurre(it4);pqA.Empurre(it5);
pq1.troca(pqA);
enquanto(!pq1.vazio())
{
custo <<pq1.principal() << '';
pq1.pop();
} custo<<' n';
enquanto(!pqA.vazio())
{
custo <<pqA.principal() << '';
pqA.pop();
} custo<<' n';
O resultado é:
& emsp; 5 & emsp; 4 & emsp; 3 & emsp; 2 & emsp; 1
& emsp; 50 & emsp; 40 & emsp; 30 & emsp; 20 & emsp; 10
A função emplace ()
o emplace () função é semelhante à função push. O código a seguir ilustra isso:
inti1= 10; inti2= 30; inti3= vinte; inti4= cinquenta; inti5= 40;
pq1.colocar(i1);pq1.colocar(i2);pq1.colocar(i3);pq1.colocar(i4);pq1.colocar(i5);
enquanto(!pq1.vazio())
{
custo <<pq1.principal() << '';
pq1.pop();
} custo<<' n';
O resultado é:
50 40 30 20 10
String Data
Ao comparar strings, a classe string deve ser usada e não o uso direto dos literais de string porque ela compararia ponteiros e não as strings reais. O código a seguir mostra como a classe string é usada:
#incluirFila de prioridade<fragmento>pq1;
string s1=fragmento('caneta'), s2=fragmento('lápis'), s3=fragmento('livro de exercícios'), s4=fragmento('livro didático'), s5=fragmento('régua');
pq1.Empurre(s1);pq1.Empurre(s2);pq1.Empurre(s3);pq1.Empurre(s4);pq1.Empurre(s5);
enquanto(!pq1.vazio())
{
custo <<pq1.principal() << '';
pq1.pop();
} custo<<' n';
O resultado é:
& emsp; livro de texto & emsp; régua & emsp; lápis & emsp; caneta & livro de exercícios emsp;
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:
vetor<int>vtr= {10,30,vinte,cinquenta,40};
Fila de prioridade<int>pq(vtr.começar(), vtr.fim());
enquanto(!pq.vazio())
{
custo <<pq.principal() << '';
pq.pop();
} custo<<' 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 construtora pegam os ponteiros de início e fim do vetor. O tipo de dados para o vetor e o tipo de dados para priority_queue devem ser iguais.
Para tornar o menor valor a prioridade, a declaração do construtor seria:
Fila de prioridade<int, vetor<int>, maior>int> >pq(vtr.começar(), vtr.fim()); Criação explícita de uma matriz
Uma fila de prioridade pode ser criada explicitamente a partir de uma matriz, como mostra o código a seguir:
Fila de prioridade<int>pq(arr, arr+5);
enquanto(!pq.vazio())
{
custo <<pq.principal() << '';
pq.pop();
} custo<<' n';
A saída é: 50 40 30 20 10. Os argumentos para a função do construtor pegam os ponteiros de início e fim 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 priority_queue devem ser iguais.
Para tornar o menor valor a prioridade, a declaração do construtor seria:
Fila de prioridade<int, vetor<int>, maior<int> >pq(arr, arr+5);Nota: Em C ++, 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 em ordem crescente ou decrescente não é a única opção para a fila de prioridade. Por exemplo, uma lista de 11 inteiros para um heap máximo é:
88, 86, 87, 84, 82, 79,74, 80, 81 ,,, 64, 69
O valor mais alto é 88. Ele é seguido por dois números: 86 e 87, que são menores que 88. O restante dos números são menores 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 menores que 86. Os números 79 e 74 são menores que 87. Os números 80 e 81 são menores que 84. Os números 64 e 69 são menores que 79.
A colocação dos números segue os critérios de heap máximo - veja mais tarde. Para fornecer tal esquema para priority_queue, o programador deve fornecer seu próprio código de comparação - veja mais tarde.
Conclusão
Um C ++ priority_queue é uma fila first-in-first-out. A função de membro, Empurre(), adiciona um novo valor à fila. A função de membro, principal(), lê o valor superior da fila. A função de membro, pop (), remove sem retornar o valor superior da fila. A função de membro, vazio(), verifica se a fila está vazia. Porém, a priority_queue difere da fila, pois segue algum algoritmo de prioridade. Pode ser maior, do primeiro ao último, ou pelo menos, do primeiro ao último. Os critérios (algoritmo) também podem ser definidos pelo programador.