Funções de fila de prioridade C ++

Funções de fila de prioridade C ++
“A fila é uma estrutura de dados FIFO (primeiro em, primeiro a sair), indicando que a inserção é colocada no final e a remoção é feita de frente. Uma variedade específica de filas é uma fila de prioridade. Ao contrário da fila, a fila de prioridade não adere ao princípio do FIFO.

As filas prioritárias são uma forma de adaptador de contêiner que é desenvolvido especialmente para que, de acordo com algumas condições rigorosas de classificação fracas, seu componente inicial seja sempre o maior dos itens que possui. Essa estrutura se assemelha a uma pilha, pois os componentes podem ser adicionados a qualquer momento, e apenas o número máximo de componentes de heap pode ser buscado (o primeiro item na lista de prioridades).

As filas prioritárias são construídas como inversores de contêineres, que são classes que utilizam uma instância fechada de uma categoria de contêiner específica como seu contêiner real e oferece um conjunto específico de variáveis ​​e funções para recuperar seus componentes. O valor mais alto da fila de prioridade, ou a “traseira” do recipiente, é de onde os componentes são empurrados.”

O que é uma fila de prioridade em C++?

O primeiro componente em uma fila de prioridade é o maior de todos os componentes da fila, e os componentes estão em ordem decrescente. Uma fila de prioridade é uma forma de adaptador de contêiner em C ++ que lida apenas com o componente de maior prioridade.

Compare uma fila com uma fila de prioridade

Não há prioridade em uma fila; Por outro lado, um recipiente de fila considera o item como tendo a principal prioridade. A primeira regra da primeira saída (FIFO) se aplica à fila; No entanto, na fila prioritária, o componente com a maior prioridade seria removido primeiro. Se vários itens tiverem uma prioridade semelhante, a ordem da fila seria usada nesta situação.

Sintaxe da fila de prioridade

A fila de prioridade em C ++ tem a seguinte sintaxe:

Os parâmetros são descritos da seguinte forma:

  • Tipo: o tipo de conteúdo ou componentes que são mantidos na fila de prioridade.
  • Container: Como a fila de prioridade é um adaptador de contêiner, sua execução requer um contêiner subjacente real. O contêiner a ser utilizado para criar a fila de prioridade é especificado por esta opção. O vetor serve como um contêiner padrão por padrão.
  • Compare: este parâmetro é opcional. Os componentes da fila de prioridade são organizados na fila de prioridade de acordo com a ordem interna de um objeto. Ele mantém as posições relativas dos itens ao compará -los. O valor possível do objeto de função é o menor, o que produz o mesmo resultado que o operador menos do que.

A fila de prioridade é construída com um max-heap por padrão em c++.

Sintaxe da fila prioritária min-heap

A criação da sintaxe Min-Heap da fila prioritária é a seguinte:

Aqui, maior é uma classe de comparação, e o vetor é um contêiner de biblioteca de modelos padrão.

Benefícios do uso da fila de prioridade

Os vértices recebem peso, o que lhes permite subir a fila em vez de cair nas costas, como estão em uma fila padrão.

Desvantagens do uso da fila de prioridade

Como também precisamos usar uma operação de adição para adicionar os itens de acordo com sua prioridade, a inserção não leva mais um período fixo de tempo, como fila. A implementação usando uma lista vinculada torna possível manter um tempo de inserção consistente.

Metodologias da fila de prioridade

As funções da fila de prioridade C ++ são as seguintes:

  • Função vazia (): este método é usado para determinar se o contêiner que mantém a fila de prioridade está em branco ou não. Retornar true se estiver vazio; falso caso contrário. Não requer argumentos.
  • Tamanho () Método: Esta função retorna a contagem de itens da fila de prioridade. O tamanho é devolvido como um número inteiro. Não requer argumentos.
  • Push () função: o item é adicionado à fila aplicando esta abordagem. O item é adicionado primeiro ao final da fila e, ao mesmo tempo, os componentes se realinham de acordo com a prioridade. Como no argumento, aceita números inteiros.
  • Função pop (): esta técnica remove o maior componente da fila de prioridade. Não requer argumentos.
  • Top () Função: O componente superior da fila de prioridade é retornado por esta função. Não requer argumentos.
  • Swap () Função: Usando esta função, uma fila de prioridade de um tamanho e tipo semelhante é trocada por seus componentes com alguma outra fila de prioridade. Ele aceita um atributo cujos números devem ser trocados e a fila de prioridade.
  • Função emplace (): com esta abordagem, um item de dados é adicionado a um contêiner na parte superior da fila. Aceita um valor de atributo.

Vamos desempenhar as funções acima mencionadas em diferentes códigos.

Exemplo nº 1

Adicionaremos um item a uma fila de prioridade neste exemplo. Para adicionar um item à fila de prioridade, utilizaremos a função push ().

Os arquivos de cabeçalho necessários e serão incorporados no início do programa. Em seguida, o espaço para nome padrão será adicionado como std. Agora a função principal () seria chamada. A fila dos valores inteiros será criada a seguir. Esta fila será uma fila de prioridade. Valores diferentes serão adicionados a esta fila de prioridade. Os números serão inseridos pelo uso da função push (). Três valores aleatórios serão adicionados utilizando o método push. A declaração "cout" será empregada para representar o texto "elementos da fila de prioridade" no console.

Depois de exibir essa linha para imprimir os valores da fila “enquanto” o loop será utilizado; Dentro do loop "while", a função vazia () será aplicada para verificar se a fila está vazia ou não. O método pop () será usado para começar a imprimir os valores da fila em ordem decrescente. Então o método pop () também é aplicado aos valores da fila. O "retorno 0" deve ser incorporado no final.

Construímos uma fila prioritária com números inteiros nomeados. A função push () foi utilizada para adicionar as diferentes entradas à fila: 12, 30 e 72.

Exemplo nº 2

Em contraste com os vetores e outras estruturas, não podemos atravessar uma fila de prioridade. Por esse motivo, imprimimos os membros da fila de prioridade usando um loop de tempo e métodos de fila de prioridade diferentes.

Isso é para que a fila de prioridade opere como uma estrutura de dados da fila de prioridade típica, e é por isso que é um adaptador de contêiner STL com acesso limitado. Como resultado, imprimimos seu topo antes de colocar periodicamente o item dentro de um loop até que a fila esteja vazia.

Exemplo no 3

Decidimos eliminar o item da fila de prioridade neste caso. A função pop () pode ser usada para excluir um componente da fila de prioridade. O valor máximo é eliminado nesta abordagem.

Iniciaremos o código integrando as bibliotecas e o espaço de nome padrão. As bibliotecas contêm e . O método para exibir a fila de prioridade seria então chamado usando Display_Priority_Queue (). A fila contém os números inteiros; portanto, "int" será fornecido como o argumento da função. Depois de tudo isso, o método principal () será invocado. A fila será criada. A função push () será utilizada para adicionar valores diferentes na fila de prioridade definida. A declaração "cout" é usada para mostrar os elementos originais da fila de prioridade.

Então o método pop () será aplicado. Esta função elimina o valor especificado da fila de prioridade. Agora, a declaração "cout" será empregada para exibir os valores da fila depois de excluir um elemento da fila. O comando "retornar 0" -seria adicionado. Em seguida, o método de utilidade será utilizado para mostrar a fila de prioridade definida. O loop "while" será empregado. Dentro dos métodos de “while” empow () e top () serão usados. A condição do loop será aplicada à função vazia (). O método pop () seria usado para excluir o valor mais alto da fila de prioridade.

Aqui, fizemos uma fila de prioridade inteira denominada num NUM. Os componentes iniciais da fila de prioridade são “61, 23, 45.”O atributo mais alto foi excluído usando a técnica pop (). Então, o resultado será “45, 23.”

Exemplo no 4

Nesse caso, a função top () será utilizada para recuperar o valor máximo da fila de prioridade.

As bibliotecas e o espaço para nome padrão serão integrados antes de começarmos a escrever o código. e estão disponíveis nas bibliotecas. Vamos então chamar a função principal (). O método de criação da fila de prioridade seria invocado. A função receberá o argumento "int" porque a fila contém apenas números inteiros. Valores diferentes serão adicionados à fila de prioridade especificada, utilizando a função push ().

POP () será usado depois que os elementos foram adicionados à fila de prioridade. Esta função mostrou o valor máximo da fila de prioridade fornecida. O texto "elemento superior da fila de prioridade" é exibido utilizando a declaração Cout. A instrução "Return 0" pode ser aplicada para encerrar o programa.

Exemplo no 5

Nesta ilustração, verificamos se a fila de prioridade está vazia ou não usando a função vazia (). Esta metodologia produz:

  • Quando a fila de prioridade não contém item, o valor 1 (true)
  • Quando a fila de prioridade contém o item 0 (false).

No início do programa, os arquivos de cabeçalho necessários e seriam incluídos. Então a STD será adicionada ao espaço de nome padrão. Agora o método principal () seria invocado. Haveria uma fila criada usando a função. Este método levará o parâmetro "String", pois contém valores com o tipo de dados "string" nesta fila. Isso terá uma prioridade. “É a fila que contém qualquer valor?”Seria impresso usando o comando“ cout ”.

A condição "se-else" seria usada para determinar a resposta. A função vazio () será aplicada dentro da declaração "se" para verificar se a fila tem valores ou não. Se a fila contiver algum valor, a declaração "cout" imprime "sim", outra instrução "cout" imprime "não" como a saída. Como resultado, a linha intitulada "Empurrando os valores da fila de prioridade" é exibida na tela pela instrução "cout". A fila de prioridade será atualizada para incluir os nomes de vários países. O método push () seria utilizado para inserir os nomes. A técnica de push adicionará os nomes de três países. “É a fila que contém qualquer valor?”Será impresso no console usando o comando“ cout ”.

A condição "se-else" será aplicada após a exibição desta linha. O método vazio () será usado mais uma vez para confirmar se a fila está vazia ou não. O último "retorno 0" deve estar presente.

Para verificar se a fila de prioridade do país está preenchida ou não, utilizamos a função vazia (). A fila está vazia no começo. País.vazio (), portanto, retorna verdadeiro. Depois disso, adicionamos itens à fila e mais uma vez utilizamos a função vazia (). Desta vez, fornece resultados falsos.

Conclusão

Primeiro, exploramos o que uma fila de prioridade em C ++ está neste artigo. Então contrastamos a fila simples com a fila de prioridade. Além disso, analisamos a sintaxe da fila prioritária, bem como seus benefícios e desvantagens. Além disso, discutimos os vários métodos C ++ para filas de prioridade. Um contêiner chamado uma fila de prioridade é usado para manter componentes com prioridades. Em contraste com as filas, que adicionam ou removem componentes de acordo com a regra do FIFO, os itens em uma fila de prioridade são excluídos de acordo com a prioridade. O componente inicial removido da fila será o único com prioridade máxima. O objetivo da fila de prioridade é gerenciar os componentes de acordo com a prioridade.

Cinco instâncias diferentes foram implementadas neste artigo. Em primeira instância, utilizamos a função push () para inserir os itens na fila de prioridade. O segundo exemplo faz uso de um loop de "tempo" para mostrar os valores da fila de prioridade. No terceiro cenário, usamos o método pop () para excluir o valor máximo da fila de prioridade. Com o auxílio da função superior (), conseguimos recuperar o maior valor na quarta ilustração. No último, empregamos o método vazio () para determinar se a fila de prioridade estava vazia ou não.