Filas prioritárias em javascript

Uma fila de prioridade é uma extensão de uma simples estrutura de dados da fila com elementos contendo um valor de prioridade, uma fila é uma coleção de elementos nos quais o primeiro elemento a entrar na fila é o primeiro elemento a sair de uma fila. Esta técnica de execução é conhecida como FIFO (primeiro dentro e primeiro a sair). Considere uma linha de pessoas do lado de fora de um caixa eletrônico, a pessoa a ficar em primeiro lugar na linha será a única a usar o caixa eletrônico primeiro. A pessoa que se une no final da fila para o caixa eletrônico será a última a usar o caixa eletrônico.

Então, agora sabemos o que é uma fila básica, mas e a fila de prioridade? Na fila de prioridade, cada elemento que entra na fila tem dois valores, um valor de prioridade e os dados. Os elementos que têm o mesmo valor de prioridade serão executados com base em FIFO (primeiro dentro e primeiro a sair) Mas elementos com maior prioridade do que outros serão executados primeiro, não importa quando foram adicionados à fila.

Este é um tópico avançado da estrutura de dados, por isso estamos assumindo que você está familiarizado com a forma como o JavaScript funciona e as funcionalidades básicas do JavaScript. Para implementar uma fila de prioridade em JavaScript, devemos primeiro saber como implementar uma fila simples em JavaScript.

Implementando uma fila em JavaScript

Os conceitos da estrutura de dados, como filas, pilhas, pilhas ou filas de prioridade, são implementados usando matrizes em javascript.

Vamos definir uma função que definirá nossa estrutura:

função fileue ()
// O código posterior será colocado dentro aqui

Sabemos que as filas são implementadas com matrizes, então vamos criar uma matriz denominada coleções

Dentro da função:

array = [];

Agora, para implementar a estrutura de dados das filas, precisamos implementar as seguintes funcionalidades:

• Enquistar: para adicionar um novo elemento no final da lista
• Dequeue: para remover o primeiro elemento da lista
• isEmpty: verificar se a fila está vazia ou não
• Tamanho: para retornar o comprimento da fila
• Frente: para retornar o valor do primeiro elemento na lista
• Impressão: Para imprimir a fila

Essas funcionalidades são facilmente adicionadas usando as seguintes linhas de código:

functionQueue ()
array = [];
esse.print = function ()
console.log (matriz);
;
esse.Enqueue = function (newmem)
variedade.push (newmem);
;
esse.dequeue = function ()
returnArray.mudança();
;
esse.front = function ()
Retorno da matriz [0];
;
esse.tamanho = function ()
returnArray.comprimento;
;
esse.isEmpty = function ()
Retornar (Array.comprimento === 0);
;

Agora, que temos nossa estrutura de dados pronta, precisamos criar um objeto mapeado para essa estrutura, fazemos isso usando a linha:

var newQueue = new fila ();

Agora, precisamos de alguns elementos a serem colocados na fila, fazemos isso usando as seguintes linhas:

NewQueue.enquistar ('a');
NewQueue.enquistar ('b');
NewQueue.enquistar ('c');

Para ver como a nossa fila parece agora, podemos chamar a função de impressão como assim:

NewQueue.imprimir();

Recebemos a seguinte saída em nosso console:

Para testar, se a implementação de primeira e primeira saída estiver funcionando corretamente, vamos desacitar um elemento da lista e imprimir o valor principal e depois imprimir a fila restante inteira com as seguintes linhas:

NewQueue.dequeue ();
console.log (newQueue.frente());
NewQueue.imprimir();

O trecho completo do código da estrutura da fila é:

functionQueue ()
array = [];
esse.print = function ()
console.log (matriz);
;
esse.Enqueue = function (newmem)
variedade.push (newmem);
;
esse.dequeue = function ()
returnArray.mudança();
;
esse.front = function ()
Retorno da matriz [0];
;
esse.tamanho = function ()
returnArray.comprimento;
;
esse.isEmpty = function ()
returnArray.comprimento === 0;
;

VarNewqueue = new Queue ();
NewQueue.enquistar ("A");
NewQueue.enquistar ("b");
NewQueue.enquistar ("c");
NewQueue.imprimir();
NewQueue.dequeue ();
console.log (newQueue.frente());
NewQueue.imprimir();

Ao executar este código, podemos observar o seguinte resultado no console:

Então, quando chamamos a função Dequeue, ele removeu o primeiro elemento da lista. Depois disso, verificamos o principal elemento na fila que foi "B". Em seguida, imprimimos a fila novamente e ela nos deu a fila restante na ordem correta. Isso significa que nossa implementação da fila está funcionando perfeitamente:

Implementando uma fila de prioridade em JavaScript

Sabemos a diferença entre uma fila normal e uma fila de prioridade é que os elementos dentro da fila de prioridade contêm um valor de prioridade junto com seus dados. Isso significa que toda a funcionalidade da fila de prioridade é a mesma que uma fila normal, exceto para o Função de enquadre.

Nas filas prioritárias, a função de enquadança coloca o elemento de prioridade mais alta antes do elemento de prioridade mais baixa. E se dois ou mais elementos tiverem a mesma prioridade, os elementos recém-adicionados serão colocados no final posterior da fila para manter um método de avaliação de primeira e primeira saída.

Portanto, tendo isso em mente, podemos escrever a nova função de enquadança para a fila de prioridade com as seguintes linhas de código:

esse.Enqueue = function (newmem)
var Array = [];
// O código posterior será colocado dentro aqui
;

A primeira coisa que fazemos na função de enoca é que, se a coleção estiver vazia, apenas empurramos o elemento para a fila:

se este.está vazia())
variedade.push (newmem);

Se a fila não estiver vazia:

• Então vamos verificar a prioridade do novo elemento com a prioridade de todos os elementos na fila
• Se a prioridade do novo elemento for menor que o elemento da coleção.O que vamos adicionar o novo elemento antes do elemento da coleção
• Isto é porque 1 significa primeira prioridade enquanto 2 significa segunda prioridade
• Se a prioridade do novo elemento maior em valor (menor em prioridade real), então vamos mudar para o final da fila e adicionar o elemento lá

outro
var adicionado = false;
para (vari = 0; iif (newmem [1] < array[i][1])
variedade.emenda (i, 0, newmem);
adicionado = true;
quebrar;


se (!adicionado)
variedade.push (newmem);

O todo enquadre A função ficará assim:

esse.Enqueue = function (newmem)
se este.está vazia())
variedade.push (newmem);
outro
var adicionado = false;
para (vari = 0; iif (newmem [1] < array[i][1])
variedade.emenda (i, 0, newmem);
adicionado = true;
quebrar;


se (!adicionado)
variedade.push (newmem);


;

O restante das funções da fila de prioridade é praticamente o mesmo que a fila normal, com uma ligeira mudança na função de dequeue para exibir apenas o nome e não o valor do elemento. Todo o trecho de código da fila de prioridade é como:

functionPriorityQueue ()
vararray = [];
esse.printCollection = function ()
console.log (matriz);
;
esse.Enqueue = function (newmem)
se este.está vazia())
variedade.push (newmem);
outro
var adicionado = false;
para (vari = 0; iif (newmem [1] variedade.emenda (i, 0, newmem);
adicionado = true;
quebrar;


se (!adicionado)
variedade.push (newmem);


;
esse.dequeue = function ()
var valor = matriz.mudança();
valor de retorno [0];
;
esse.front = function ()
returnArray [0];
;
esse.tamanho = function ()
returnArray.comprimento;
;
esse.isEmpty = function ()
returnArray.comprimento === 0;
;

Hora de colocar elementos na fila usando as seguintes linhas de código:

var pq = new priorityQueue ();
pq.enquistar (["google", 2]);
pq.enquistar (["bing", 3]);
pq.enquistar (["Microsoft", 1]);
pq.enquistar (["maçã", 2]);
pq.printCollection ();

Como você pode ver, a primeira prioridade é o “Microsoft” elemento com valor 1. Deve estar no início da fila, mesmo que tenha sido adicionado no 3º lugar.

Agora, se chamarmos a função Dequeue e, em seguida, a função de impressão novamente, o primeiro elemento deve ser removido da lista:

pq.dequeue ();
pq.printCollection ();

Lá está você, nossa fila de prioridade está funcionando perfeitamente.

Conclusão

Filas são conceitos de estrutura de dados que funcionam no método de avaliação de primeiro e primeiro a sair. Da mesma forma, filas prioritárias funcionam sobre a avaliação do primeiro e primeiro a sair, mas com um valor extra de "prioridade", o elemento com a maior prioridade será executado primeiro, não importa quando foram adicionados à fila. Neste post, aprendemos a implementar uma fila simples em JavaScript e como usar essa estrutura de dados para implementar o funcionamento de uma fila de prioridade.