Fila prioritária em java
No dia seguinte, as mesmas três pessoas vieram. Desta vez, seu amigo está no meio. Você decidiu servi -lo primeiro, à frente da pessoa que veio primeiro, depois a terceira pessoa e, finalmente, a primeira pessoa. Então, desta vez, de acordo com o robô, a posição 2 tem a maior prioridade, seguida pela posição 3.
No terceiro dia, seu amigo é o primeiro e você faz o primeiro-come_first serve. A conclusão de qualquer pessoa e do robô é que a prioridade depende de quem está preocupado e da posição de cada pessoa. NOTA: Na vida real, a prioridade nem sempre depende de primeiro-come_first serve.
Na programação, uma fila de prioridade binária é onde o primeiro item tem a maior prioridade. O terceiro item pode ter maior prioridade e o segundo item, a terceira prioridade. As filas prioritárias são de natureza binária. Nota: O primeiro item é sempre a maior prioridade em uma fila de prioridade. Também pode acontecer que o segundo item tenha maior prioridade e o terceiro item tem a terceira prioridade. Na definição da fila de prioridade, as prioridades do segundo e terceiro itens podem não estar em ordem decrescente. Essa diferença continua na fila até o último item, que pode não ser o menor item de prioridade. No entanto, estará entre os da menor prioridade. Este setor parcial também é conhecido como ordem parcial. Portanto, uma fila de prioridade é uma fila de ordenação parcial, onde a prioridade não é o primeiro-come_first serve, embora essa seja a regra geral.
Ao lidar com a matriz, o primeiro-come_first serve é o primeiro in_first-out, escrito como FIFO. Na computação, a fila é FIFO, enquanto a fila de prioridade é um FIFO parcial porque, à medida que a fila está descendo, alguns itens têm prioridades maiores que seus predecessores próximos. À medida que a fila de prioridade desce ainda mais, a distância entre esses predecessores próximos e as prioridades mais altas aumenta.
Uma fila de prioridade é implementada como uma estrutura de dados de heap. A próxima pergunta é: o que é uma pilha? Existe a pilha máxima e a pilha mínima, que será discutida em detalhes abaixo.
Conteúdo do artigo
- Estrutura de dados de heap
- Fila prioritária em java apropriado
- Java Construção de uma fila prioritária
- Métodos Java de uma fila prioritária
- Conclusão
Estrutura de dados de heap
Há max-heap, e há min-heap. Com Max-heap, o primeiro item é o maior valor. À medida que a fila é descendente, os valores continuam a diminuir, aumentar e geralmente diminuir. Com o min-heap, o primeiro item é o menor valor. À medida que a fila desce, os valores continuam aumentando e diminuindo e geralmente aumentam. Os valores de um heap podem ser mantidos em uma matriz.
Uma pilha binária é onde um nó (item) tem dois filhos. O primeiro filho é o filho esquerdo e o segundo filho é o filho certo. O valor de qualquer nó é chamado de chave.
Max-heap
A lista a seguir é um max-heap que já é parcialmente ordenado e não precisa de mais pedidos:
89, 85, 87, 84, 82, 79, 73, 80, 81 ,, 65, 6989 é o primeiro valor no índice 0. É o nó raiz (pai raiz). É o maior valor entre todos os valores. Seu primeiro filho (85) está no índice 1, cujo índice é igual a 2 (0) + 1, onde 0 é o índice do pai. Seu segundo filho (87) está no índice 2, que é igual a 2 (0) + 2, onde 0 é o índice do pai.
85 está no índice 1. É um pai. Seu primeiro filho (84) está no índice 3, que é igual a 2 (1) + 1, onde 1 é o índice do pai. Seu segundo filho (82) está no índice 4, que é igual a 2 (1) + 2, onde 1 é o índice do pai.
87 está no índice 2. É um pai. Seu primeiro filho (79) está no índice 5, que é igual a 2 (2) + 1, onde 2 é o índice do pai. Seu segundo filho (73) está no índice 6, que é igual a 2 (2) + 2, onde 2 é o índice do pai.
Em geral, quando a contagem de índices começa a partir de 0, eu represento o índice de um pai da matriz; E assim, o filho esquerdo (primeiro) de um pai no índice I está no índice 2i + 1; e sua criança certa (segunda) está no índice 2i + 2. Algumas células no final da matriz podem estar vazias; Eles não devem ter valores.
A lista anterior é um bom exemplo do conteúdo de uma fila prioritária depois que toda a inclusão de elementos está completa. Se o primeiro elemento for removido, o restante será reorganizado para configurar os valores, formando uma nova fila de prioridade. Dessa forma, remover todos os elementos do topo pareceria como se todos os elementos fossem classificados corretamente. Os elementos ainda podem ser obtidos como são, em uma ordem parcial, sem remover nenhum elemento.
Min-heap
Min-heap é o inverso de Max-heap.
Fila prioritária em java apropriado
Java tem uma aula chamada PriorityQueue, para prioridade. Tem muitos construtores e métodos. Apenas três construtores e os métodos mais apropriados são explicados abaixo:
Java Construção de uma fila prioritária
PIRIORITYQUEUE PUBLICO ()
Isso cria uma fila de prioridade sem nenhum elemento. A classe, PriorityQueue, está no java.util.* pacote, que deve ser importado. O segmento de código a seguir cria uma prioridade vazia e, em seguida, adiciona valores não classificados (nem parcialmente classificados) à fila:
Fila de prioridadepq.add (69); pq.add (65); pq.add (87); pq.add (79);
pq.add (73); pq.add (84); pq.add (89); pq.add (80);
pq.add (81); pq.add (82); pq.add (85);
Esses números são todos inteiros. Eles são da lista parcialmente classificada fornecida acima, mas atualmente, eles são completamente não classificados quando são inseridos. Os elementos em PQ agora são parcialmente classificados de acordo com a definição da fila de prioridade em Java.
PriorityQueue Public (PriorityQueue C)
Isso cria uma prioridade de outra prioridade. O seguinte segmento de código ilustra o seguinte:
Fila de prioridadepq.add (69); pq.add (65); pq.add (87); pq.add (79);
pq.add (73); pq.add (84); pq.add (89); pq.add (80);
pq.add (81); pq.add (82); pq.add (85);
Fila de prioridade
PQ1 foi criado a partir de PQ. Atualmente tem o mesmo pedido parcial e PQ.
O terceiro método construtor é ilustrado abaixo.
Métodos Java de uma fila prioritária
Public int size ()
Isso retorna o tamanho da lista e não inclui células vazias, conforme ilustrado no código a seguir:
Fila de prioridadepq.add (69); pq.add (65); pq.add (87); pq.add (79);
pq.add (73); pq.add (84); pq.add (89); pq.add (80);
pq.add (81); pq.add (82); pq.add (85);
int sz = pq.tamanho();
Sistema.fora.println (sz);
A saída é 11.
Public void foreach (ação do consumidor)
Este método precisa ser usado de uma maneira especial para copiar todos os valores na fila de prioridade na forma parcialmente classificada. O programa a seguir ilustra o seguinte:
Fila de prioridadepq.add (69); pq.add (65); pq.add (87); pq.add (79);
pq.add (73); pq.add (84); pq.add (89); pq.add (80);
pq.add (81); pq.add (82); pq.add (85);
pq.foreach (item -> sistema.fora.impressão (item + ""));
Sistema.fora.println ();
Observe a maneira como o código dentro dos parênteses do método foreach foi feito. O item é uma variável dummy que representa cada elemento na fila. Observe o uso do operador de seta. A saída é:
65 69 84 79 73 87 89 80 81 82 85A saída está correta, em uma ordem parcial, mas em uma ordem ascendente. Esta não é necessariamente a ordem inversa dada acima devido à maneira como os valores foram incluídos na lista. Isto é, o método foreach retorna a lista como um min-heap. Para devolver a lista em ordem decrescente, use o seguinte construtor:
PriorityQueue do público (comparador do comparador)
Este é um construtor. O código a seguir mostra como usá -lo:
Fila de prioridadepq.add (69); pq.add (65); pq.add (87); pq.add (79);
pq.add (73); pq.add (84); pq.add (89); pq.add (80);
pq.add (81); pq.add (82); pq.add (85);
pq.foreach (item -> sistema.fora.impressão (item + ""));
Os x, y são variáveis dummy representando os menores e menos valores. Observe que nos primeiros parênteses para x e y, x vem antes de y. Nos segundos parênteses, Y vem antes de x. A saída é:
89 85 87 80 82 69 84 65 79 73 81Public boolean add (e e)
O número de elementos em uma fila de prioridade pode ser aumentado um por um. Este método retorna verdadeiro se uma alteração ocorrer; e falso caso contrário. O código a seguir agrega o décimo segundo valor prático à fila:
Fila de prioridadepq.add (69); pq.add (65); pq.add (87); pq.add (79);
pq.add (73); pq.add (84); pq.add (89); pq.add (80);
pq.add (81); pq.add (82); pq.add (85); pq.add (70);
pq.foreach (item -> sistema.fora.impressão (item + ""));
O valor agregado aumentaria a fila para se encaixar em sua posição apropriada, levando a algum reajuste de posições de elemento. A saída é:
89 85 87 80 82 70 84 65 79 73 81 69Pesquisa pública ()
Este método recupera e remove a cabeça da fila; ou retorna nulo, se esta fila estiver vazia. Cada vez que a cabeça é removida, a fila de prioridade se reajusta para ter uma nova cabeça de direito. Se a cabeça continuar a ser removida, os valores retornados serão em ordem completa classificada. O código a seguir ilustra o seguinte:
Fila de prioridadepq.add (69); pq.add (65); pq.add (87); pq.add (79);
pq.add (73); pq.add (84); pq.add (89); pq.add (80);
pq.add (81); pq.add (82); pq.add (85); pq.add (70);
pq.foreach (item -> sistema.fora.Imprimir (Pq.Poll () + ""));
A saída do computador do autor é:
89 87 85 84 82 81 80 79 73 70 69 65 Exceção no tópico Java "principal".util.ConcurrentModificationExceptionem Java.base/java.util.Fila de prioridade.foreach (PriorityQueue.Java: 984)
em TheClass.Principal (TheClass.Java: 11)
Observe que a saída é de ordem classificada completa. Este código em particular não pôde pegar a exceção lançada. Esta questão é deixada como um exercício de pesquisa para o leitor.
Conclusão
Uma fila de prioridade em Java é uma fila em que os elementos têm prioridade diferente de FIFO. Uma fila de prioridade é tipicamente uma pilha, que pode ser o máximo ou o mínimo. Os valores devem ser do mesmo tipo. Eles são armazenados na fila em formato de heap (ordem parcial). Esperamos que você tenha achado este artigo útil. Confira os outros artigos de dica do Linux para obter dicas e tutoriais.