1. Estrutura de dados de prioridade
A estrutura de dados do PriorityQueue (fila de prioridade) no JDK7 é uma pilha binária. Para ser preciso, é uma menor pilha.
Uma pilha binária é uma pilha especial, que é aproximadamente uma árvore binária completa. O heap binário satisfaz as características: o valor -chave do nó pai sempre mantém um relacionamento de ordem fixa com o valor da chave de qualquer nó filho, e a subárvore esquerda e a subárvore direita de cada nó são uma pilha binária.
A pilha máxima é quando o valor da chave do nó pai é sempre maior ou igual ao valor -chave de qualquer nó filho. A pilha mínima é quando o valor da chave do nó pai é sempre menor ou igual ao valor -chave de qualquer nó filho.
A figura a seguir é uma pilha máxima
O cabeçalho da equipe PriorityQueue é o menor elemento da ordem dada.
O PriorityQueue não permite valores nulos e não suporta objetos não comparáveis. O PriorityQueue requer o uso de interfaces comparáveis e comparador para classificar objetos, e os elementos neles serão processados de acordo com a prioridade ao classificar.
O tamanho do PriorityQueue é ilimitado, mas o tamanho inicial pode ser especificado quando criado. Ao adicionar elementos da fila, a fila se expande automaticamente.
O PriorityQueue não é seguro para encadeamentos, o PriorityBlockEue semelhante é seguro para roscas.
Sabemos que as filas seguem o primeiro modo de primeira saída, mas às vezes os objetos precisam ser processados com base na prioridade na fila. Por exemplo, temos um aplicativo que gera relatórios de ações durante o horário de negociação diário, o que requer processamento de muitos dados e leva muito tempo de processamento. Quando o cliente envia uma solicitação para este aplicativo, ele realmente entra na fila. Precisamos lidar com clientes prioritários primeiro e depois com usuários comuns. Nesse caso, a prioridade de Java (fila de prioridade) será muito útil.
PriorityQueue é uma fila ilimitada com base na pilha de prioridade. Os elementos nesta fila de prioridade podem ser classificados naturalmente por padrão ou classificado quando a fila é instanciada pelo comparador fornecido.
As filas prioritárias não permitem valores nulos e não suportam objetos não comparáveis, como classes definidas pelo usuário. A fila de prioridade requer o uso de interfaces comparáveis e comparador de Java para classificar objetos, e os elementos neles serão processados de acordo com a prioridade ao classificar.
O cabeçalho da fila de prioridade é o menor elemento baseado em classificação natural ou classificação do comparador. Se vários objetos tiverem o mesmo tipo, é possível levar algum deles aleatoriamente. Quando obtemos a fila, retornamos o objeto de cabeçalho da fila.
O tamanho da fila de prioridade é irrestrito, mas o tamanho inicial pode ser especificado no momento da criação. Quando adicionamos elementos à fila de prioridade, o tamanho da fila aumentará automaticamente.
O PriorityQueue é não seguro, portanto, o Java fornece PriorityBlockingQueue (implementando a interface BlockingQueue) para ambientes com vários threads Java.
2. Análise de código -fonte PriorityQueue
membro:
Objeto transitório Priavte [] fila; private int size = 0;
1. O processo de construção de uma pequena pilha superior por priorityQueue
Aqui, usamos o construtor PriorityQueue para passar em um contêiner como o parâmetro priorityQueue (coleta <? Estende e> exemplo:
O processo de construção de um pequeno monte superior é dividido em duas etapas:
Copie dados de contêiner e verifique se os dados do contêiner são nulos
Iniciações de void privado de fromCollection (coleção <? Extende e> c) {object [] a = c.toarray (); // Se c.toArray incorretamente não retornar objeto [], copie -o. if (a.getclass ()! = objeto []. classe) a = arrays.copyof (a, a.Length, objeto []. classe); int len = A.Length; if (len == 1 || this.comparator! = nulo) para (int i = 0; i <len; i ++) se (a [i] == null) lança novo nullPointerException (); this.queue = a; this.size = A.Length;} Ajuste para fazer com que os dados satisfazem a estrutura da pequena pilha superior.
Primeiro, dois métodos de ajuste: Siftup e Siftdown
SIFTDOWN: Quando um elemento de inicialização é fornecido, o elemento deve ser ajustado para que atenda às propriedades estruturais da pilha mínima. Portanto, o valor da chave do elemento X é constantemente comparado e trocado com a criança de cima para baixo até que se descobre que o valor da chave do elemento X é menor ou igual ao valor -chave da criança (ou seja, é garantido que seja menor que seus valores de nó esquerdo e direito), ou cai no nó da folha.
Por exemplo, como mostrado no diagrama a seguir, ajuste este nó 9:
private void siftDownComparable (int k, e x) {comparável <? super e> chave = (comparável <? super e>) x; int metade = tamanho >>> 1; // tamanho/2 é o subscrito do primeiro nó da folha //, desde que o nó foliar não seja atingido enquanto (k <metade) {int filho = (k << 1) + 1; // Objeto infantil esquerdo C = fila [filho]; int certo = criança + 1; // Descubra os filhos menores e menores das crianças esquerda e direita (direita <tamanho && ((comparável <? Super e>) c) .compareto ((e) fila [direita])> 0) c = fila [filho = direita]; if (key.compareto ((e) c) <= 0) quebrar; fila [k] = c; k = criança; } fila [k] = key;} SIFTUP: PriorityQueue insere o novo elemento na cauda cada vez que um novo elemento é adicionado. Portanto, deve haver o mesmo processo de ajuste que o SIFTDOWN, exceto para se ajustar do fundo (folha) para cima.
Por exemplo, preencha o nó com a Key 3 no diagrama a seguir:
private void siftupComparable (int k, e x) {comparável <? super e> chave = (comparável <? super e>) x; while (k> 0) {int parent = (k - 1) >>> 1; // Obter objeto subscrito dos pais e = fila [pai]; if (key.compareto ((e) e)> = 0) quebra; fila [k] = e; k = pai; } fila [k] = key;}O processo geral de construção de uma pequena pilha superior é:
private void initfromCollection (coleção <? Extends e> c) {initElementsFromCollection (c); pesado(); }Entre eles, Heapify está o processo de peneira.
2. PriorityQueue Capacity Expansion Process
Como pode ser visto nos membros da instância, o PriorityQueue mantém um objeto [], portanto, seu método de expansão é semelhante à lista de Arraylist da tabela de pedidos.
Somente o código -fonte do método de crescimento é fornecido aqui
Void privado Grow (int mincapacity) {int OldCapacity = fileue.length; // tamanho duplo se pequeno; mais crescer em 50% int newcapacity = antigoCapacidade + ((antiga capacidade <64)? (OldCapacity + 2): (OldCapacity >> 1)); // Código consciente do Overflow if (newCapacity - max_array_size> 0) newCapacity = hugecapacity (MINCAPACIDADE); fila = arrays.copyof (fila, nova capacidade); }Pode -se observar que, quando a capacidade da matriz não é grande, a capacidade não é grande sempre. Quando a capacidade da matriz é superior a 64, o dobro é expandido a cada vez.
3. Aplicação de prioridade
EG1:
Aqui está o aplicativo mais simples: encontre o maior número de dados dinâmicos.
A idéia é manter uma pequena pilha superior com tamanho = k.
// dados são dados dinâmicos // heap mantém dados dinâmicos // res é usado para salvar o valor Kthlar MAI mais público (int k, priorityQueue <Teger> heap, int [] res) {if (heap.size () <k) {heap.offer (data); if (heap.size () == k) {res [0] = heap.peek (); retornar true; } retornar false; } if (heap.peek () <data) {heap.poll (); heap.offer (dados); } res [0] = heap.peek (); retornar true; }
EG2:
Temos um cliente da classe de usuário que não fornece nenhum tipo de tipo. Quando o usamos para criar uma fila de prioridade, devemos fornecer um objeto comparador.
Customer.java
pacote com.journalDev.Collections; CLASSION Public CLIENTE {private Int ID; nome de string privado; cliente público (int i, string n) {this.id = i; this.name = n; } public int getId () {return id; } public string getName () {return name; }} Usamos números aleatórios Java para gerar objetos de usuário aleatórios. Para classificação natural, usamos objeto inteiro, que também é um objeto Java encapsulado.
Aqui está o código de teste final mostrando como usar PriorityQueue:
PriorityQueeExample.java
pacote com.journalDev.Collections; importar java.util.comparator; importar java.util.priorityQueue; importar java.util.queue; importar java.util.random; classe pública PriorityQueeExample {public static void main (string [] args) {// fila de prioridade Exemplo de classificação natural na fila <Teger> integerPriorityQueue = new priorityQueue <> (7); Rand aleatório = novo aleatório (); for (int i = 0; i <7; i ++) {integerPriorityQueue.add (novo número inteiro (rand.nextint (100))); } para (int i = 0; i <7; i ++) {integer in = integerPriorityQueue.poll (); System.out.println ("Processamento inteiro:"+in); } // fila de fila prioritária Exemplo de fila <lusteral> cliente priorityQueue = new priorityQueue <> (7, IdComParator); addDatatoqueue (CustomerPriorityQueue); PollDataFromqueue (CustomerPriorityQueue); } // Anonymous Comparator implementa o comparador estático público <ctormer> idComParator = new Comparator <flowener> () {@Override public Int Compare (cliente c1, cliente c2) {return (int) (c1.getId () - c2.getId ()); }}; // Método universal usado para adicionar dados à fila privada estática vazio addDatatoqueue (fila <lusteral> clientepriorityQueue) {aleather rand = new Random (); for (int i = 0; i <7; i ++) {int id = rand.nextint (100); CustomerPriorityQueue.add (novo cliente (id, "pankaj"+id)); }} // Método geral para buscar dados de uma fila private estático vazio poldDataFromqueue (fila <lusteral> clientePriorityQueue) {while (true) {cliente custa = clientpriorityQueue.poll (); if (cust == null) quebra; System.out.println ("Processando o cliente com id ="+cust.getId ()); }}}} Observe que eu uso a classe Java Anonymous que implementa a interface do comparador e implementa um comparador baseado em ID.
Quando executo o programa de teste acima, recebo a seguinte saída:
Processamento Inteiro: 9 PROCESSÃO INTEIRA: 16 PROCESSÃO INTEIRA: 18 PROCESSÃO INTERGENTES: 25 PROCESSING INTEGER: 33 PROCESSING INTERGER: 75 PROCESSING INTEGER: 77Processing Cliente com cliente = 6Processing Client = 20Cessing Client com ID = 24 ID = 82 PROCESSING CLIENTE COM ID = 96
A partir dos resultados da saída, pode -se ver claramente que o menor elemento é então retirado primeiro na cabeça da fila. Se o comparador não for implementado, será lançada uma classe ClassCException ao criar um cliente de prioridade.
Exceção no tópico "main" java.lang.classCastException: com.journalDev.collections.customer não pode ser lançado para java.lang.comparable em java.util.priorityQueue.siftupComParable (priorityQueue.java:633) em java.util.priorityueeee.sifteue.java:633) em java.util.priorityeuee.SiftEue.SiftEue.SiftEue.SiftEue.Java:633) java.util.priorityQueue.offer (priorityQueue.java:329) em java.util.priorityQueue.add (priorityQueue.java:306) em com.journalDeexemex.java.priorityqueeexample.addatatoqueue (prioritáriaeexempam.java com.journalDev.collection.priorityQueeExample.main (priorityqueeexample.java:25)