PriorityQueue

De onde foi essa questão?

Quando você executa o método poll ele irá recuperar e remover o primeiro(de acordo com a prioridade) da fila.

PriorityQueue utiliza ou ordenamento natural ou um ordenamento definido pelo usuário. E o metodo poll retorna a maior prioridade removendo da fila.

Primeiro vc só imprime os elementos contido dentro de inter.
Segundo vc retira o elemento de maior prioridade.
Terceiro vc reezibe a sua fila.

Kra tem algum erro ai por não usar a inerface Comparable. Não sei explicar isso. Mas a documentação fala sobre o ordenamento natural não utlizando Comparable.

é cara intaun eu não entendi tbm mais juro executo assim aqui na minha máquina

Ola.
Pelos meus teste ele só classifica a primeira prioridade quando há offer(), deve ser para caso tu chame um peek().
Mas quando tú realiza um poll() ele ordena todos.
Talvez realize ações como essa para evitar o overhead

mateusbrum:

Ola.
Pelos meus teste ele só classifica a primeira prioridade quando há offer(), deve ser para caso tu chame um peek().
Mas quando tú realiza um poll() ele ordena todos.
Talvez realize ações como essa para evitar o overhead

Mateu se prestar atenção vai perceber que a ordem dele de inserção é a seguinte. 15, 14 e 11, ou seja, uma ordem inversa da natual. Quando ele exibe a primeira vez ele exibe em uma ordem que deveria ser a natural mas não está sendo. A diferença entre peek() e poll é que peek() retorna o elemento de prioridade mais alta sem remover e poll() retorna o mesmo removendo.
Se por acaso vc fizer um teste e trocar poll() por peek() vai perceber que a saida vai ser mesma exibida na primeira vez.

public static void main(String[] args) {
		Queue<Integer> q = new PriorityQueue<Integer>();
		q.add(19);
		q.add(18);
		q.add(15);
		q.add(12);
		q.add(11);
		
		System.out.println(q);
		System.out.println(q.peek());
		System.out.println(q);
		System.out.println(q.poll());
		System.out.println(q);		
	}

Anderson, realizando os testes acima que eu conclui isso (posso e devo estar errado), as saídas foram:
[11, 12, 18, 19, 15]
11
[11, 12, 18, 19, 15]
11
[12, 15, 18, 19]

Ou seja sempre a fila insere o primeiro elemento pela inportância (tavez para não ter que processar quando se usa algum método de manipulação, já que isso sempre resulta em manipular o primeiro elemento), e só posteriormento quando se remove um objeto com peek ou remove ele classifica a fila, já que talvez isso ocorreria posteriormente com maior frequência :D

Bom isso é apenas uma especulação, olhei no documento e não ache !

Kra eu sinceramente não entendi muito oq vc quiz dizer, mas a K&B fala que PriorityQueue utiliza um tipo de fila que eu denominei de PIPO "Priority in Priority out" ela fala também que vc pode utilizar seu próprio ordenamento implementando a interface Comparable ou utilizando a ordem natural onde por exemplo 1 tem maior prioridade que 2.

Queue<Integer> q = new PriorityQueue<Integer>();  
		q.add(19);  
		q.add(18);  
		q.add(15);  
		q.add(12);  
		q.add(11);  

		System.out.println(q);  
		System.out.println(q.peek());  
		System.out.println(q);  
		System.out.println(q.poll());  
		System.out.println(q);
                
                q.add(8);
		System.out.println(q);

O resultado foi:
[11, 12, 18, 19, 15]
11
[11, 12, 18, 19, 15]
11
[12, 15, 18, 19]
---------------------------
[8, 12, 18, 19, 15]

15 não teria mais prioridade que 18? heheh Bem estranho isso.
:roll:

Realmete, muito estranho!
Pois antes de tu inserir algo, o Queue já estava classificado, não seria mais fácil para o compilador manter tudo classificado e inserir o novo elemento no local correto, ou esse resultado seria a bagunça que a fila faz para arrumar o primeiro elemento? :? :shock:
Reforço que acho que sempre o primeiro elemento vai estar classificado, pois seria para evitar overhead no momento de utilizar os métodos de manipulação!

Oi pessoal,
A documentacao nao diz que PrioriyQueue mantem a lista ordenada (sorted) certo?

O que acontece eh que no momento de recuperar os elementos, eles sao recuperados pela prioridade, que no caso, eh pela ordenacao natural.

Nao seria isso?

Depois de muito estudar a forma de como é feito essa classificação que a K&B diz ser de forma natural eu cheguei a seguinte conclusão:

No momento em que vai ser inserido ele verifica se é menor que a primeira posição. Se for ele insere no inicio e faz um ordenamento com troca de posições mantendo a primeira posição inalteravel.
Se for maior ele insere no final. E não faz ordenamento nenhum. E se for um numero que não é nem menor que a primeira posição e nem maior que a ultima ele insere no final e novamente não faz ordenamento nehum.
Segue meu exemplo que me fez chegar a esta conclusão:

Queue<Integer> q = new PriorityQueue<Integer>(); 
q.add(8);
System.out.println(q);		
q.add(7);
System.out.println(q);		
q.add(6);
System.out.println(q);		
q.add(5);
System.out.println(q);		
q.add(4);
System.out.println(q);		
q.add(3);
System.out.println(q);		
q.add(2);
System.out.println(q);		
q.add(1);
System.out.println(q);		
q.add(10);
System.out.println(q);		
q.add(9);
System.out.println(q);

Resultado:
[8]
[7, 8]
[6, 8, 7]
[5, 6, 7, 8]
[4, 5, 7, 8, 6]
[3, 5, 4, 8, 6, 7]
[2, 5, 3, 8, 6, 7, 4]
[1, 2, 3, 5, 6, 7, 4, 8]
[1, 2, 3, 5, 6, 7, 4, 8, 10]
[1, 2, 3, 5, 6, 7, 4, 8, 10, 9]

Não sei se ajuda a esclarecer as dúvidas, mas verifiquei o código do sdk e vejam só:

public boolean offer(E e) {
        if (e == null)
            throw new NullPointerException();
        modCount++;
        int i = size;
        if (i >= queue.length)
            grow(i + 1);
        size = i + 1;
        if (i == 0)
            queue[0] = e;
        else
            siftUp(i, e);
        return true;
    }

no caso apresentado ele chama sempre o siftUp.

private void siftUp(int k, E x) {
        if (comparator != null)
            siftUpUsingComparator(k, x);
        else
            siftUpComparable(k, x);
    }

private void siftUpComparable(int k, E x) {
        Comparable<? super E> key = (Comparable<? super E>) x;
        while (k > 0) {
            int parent = (k - 1) >>> 1;
            Object e = queue[parent];
            if (key.compareTo((E) e) >= 0)
                break;
            queue[k] = e;
            k = parent;
        }
        queue[k] = key;
    }

Nesse exemplo, quando se tem quantidade elementos ímpares na queue a probabilidade de erro é menor, vejamos:
a situação de ter os dois primeiros elementos [14,15] e sendo inserido o elemento 11.
o método siftUpComparable é chamado recebendo os parâmetros: 2 e 11
Observe então que k tem o valor 2, logo em seguida parent receberá 0 e key tem o valor 11.

Nessa linha if (key.compareTo((E) e) >= 0) ocorrerá a comparação de 11.compareTo(14) que retornará 1 e será >= 0, logo break, sai do laço e a inserção ocorre na última posição, ou seja, a queue fica com os valores:
[14,15,11]
E depois no siftDown ocorre a inversão de 14 com 11.

Outras partes da sdk:

public boolean add(E e) {
        return offer(e);
    }

public E peek() {
        if (size == 0)
            return null;
        return (E) queue[0];
    }

    public E poll() {
        if (size == 0)
            return null;
        int s = --size;
        modCount++;
        E result = (E) queue[0];
        E x = (E) queue[s];
        queue[s] = null;
        if (s != 0)
            siftDown(0, x);
        return result;
    }

    private void siftDown(int k, E x) {
        if (comparator != null)
            siftDownUsingComparator(k, x);
        else
            siftDownComparable(k, x);
    }

    private void siftDownComparable(int k, E x) {
        Comparable<? super E> key = (Comparable<? super E>)x;
        int half = size >>> 1;        // loop while a non-leaf
        while (k < half) {
            int child = (k << 1) + 1; // assume left child is least
            Object c = queue[child];
            int right = child + 1;
            if (right < size &&
                ((Comparable<? super E>) c).compareTo((E) queue[right]) > 0)
                c = queue[child = right];
            if (key.compareTo((E) c) <= 0)
                break;
            queue[k] = c;
            k = child;
        }
        queue[k] = key;
    }

Esse é a forma de atuação dos algoritmos otimistas, observem que na operação de siftDownComparable, ele reposiciona o último elemento, na realidade o método é chamado passando os valores 0 e o valor da última posição da queue.

O erro é gerado na inserção e corrigido na remoção, mas tanto no melhor caso, quanto no pior, o elemento de "maior prioridade" encontra-se sempre na posição 0 da queue.

fw

Obs:
▪ Algoritmos Otimistas: Permite a ocorrência da inconsistência, porém toma medidas para sua correção.

[editado]
Ops: já na primeira inserção ocorreu o erro, ou seja, a queue estava com [15,14] quando foi chamado o método offer com o argumento 11.
[/editado]

Quando se tenta inserir um número ele verifica se é menor do que o número existente na primeira posição, se é menor e insere no inicio e em seguida realiza um ordenamento. As inserções no inicio foram:
[8]
[7, 8]
[6, 8, 7]
[5, 6, 7, 8]
[4, 5, 7, 8, 6]
[3, 5, 4, 8, 6, 7]
[2, 5, 3, 8, 6, 7, 4]
[1, 2, 3, 5, 6, 7, 4, 8]

Se o númerio for maior que o da primeira posição então ele insere no final e não realiza ordenamento nenhum. A tentativa de inserção foi o número 10:
[1, 2, 3, 5, 6, 7, 4, 8, 10]

Se o número não for nem menor que o número da primeira posição e nem maior que a da ultima posição ainda sim ele insere no final e novamente não realiza ordenamento nenhum. A tentativa de inserção foi o número 9:
[1, 2, 3, 5, 6, 7, 4, 8, 10, 9]

Obs: Não consegui entender como funciona o ordenamento.

Pessoal o PriorityQueue quando chamando System.out.println(…) chamará o metodo toString() para imprimir os elementos. tenham em mente que o PriorityQueue ordena os elementos em ordem natural isto é 1 antes de 2, 2 antes de 3, a não ser que nos passamos um comparator para o construtor do mesmo. Embora a chamada a System.out.println() não esteja ordenado é por que PriorityQueue extends AbstractQueue e AbstractQueue extends AbstractCollection.
AbstractCollection.toString() “retorna uma representação de uma string atravez de um iterator” sendo que este iterator não garante a ordem dos elementos .
Valew." :twisted:

Beleza Raff,

de fato no javadoc está descrito:

(...)
* this class and its iterator implement all of the
* <em>optional</em> methods of the {@link Collection} and {@link
* Iterator} interfaces. The Iterator provided in method {@link
* #iterator()} is <em>not</em> guaranteed to traverse the elements of
* the priority queue in any particular order. If you need ordered
* traversal, consider using {@code Arrays.sort(pq.toArray())}.
(...)

Mas o erro, acredito que realmente aconteça, porque se você buscar verificar os métodos que descrevi eles realmente possuem falhas (previstas e tratadas, mas elas estão lá e são fáceis de verificar):

public static void main(String[] args) {
        // TODO code application logic here
        java.util.PriorityQueue<Integer> qMax = new java.util.PriorityQueue<Integer>();
        java.util.PriorityQueue<Integer> qMin = new java.util.PriorityQueue<Integer>();
        Integer um = 1;
        Integer dois = 2;
        Integer cinco = 5;
        Integer oito = 8;
        Integer dez = 10;
        System.out.println("Situação com apenas 1 elemento: ");
        qMax.add(cinco);
        qMin.add(cinco);
        System.out.println("Max:"+qMax);
        System.out.println("Min:"+qMin);
        qMax.add(oito);
        qMin.add(dois);
        System.out.println("Max:"+qMax);
        System.out.println("Min:"+qMin);
        qMax.add(dez);
        qMin.add(um);
        System.out.println("Max:"+qMax);
        System.out.println("Min:"+qMin);
        
        Object[] array = qMin.toArray();
        for(Object o : array ) {
            System.out.println(o);
        }
    }

Saída produzida:

Situação com apenas 1 elemento:
Max:[5]
Min:[5]
Max:[5, 8]
Min:[2, 5]
Max:[5, 8, 10]
Min:[1, 5, 2]
1
5
2

private transient Object[] queue;
    //(..)
    public Object[] toArray() {
        return Arrays.copyOf(queue, size);
    }

Um detalhe de menor importância, a classe interna que implementa o iterator de PriorityQueue utiliza um ArrayDeque sem ordenação, logo os elementos ficam na mesma posição que estavam no vetor interno queue.

fw

doido neh

anderson.bonavides:

Quando se tenta inserir um número ele verifica se é menor do que o número existente na primeira posição, se é menor e insere no inicio e em seguida realiza um ordenamento. As inserções no inicio foram:
[8]
[7, 8]
[6, 8, 7]
[5, 6, 7, 8]
[4, 5, 7, 8, 6]
[3, 5, 4, 8, 6, 7]
[2, 5, 3, 8, 6, 7, 4]
[1, 2, 3, 5, 6, 7, 4, 8]

Se o númerio for maior que o da primeira posição então ele insere no final e não realiza ordenamento nenhum. A tentativa de inserção foi o número 10:
[1, 2, 3, 5, 6, 7, 4, 8, 10]

Se o número não for nem menor que o número da primeira posição e nem maior que a da ultima posição ainda sim ele insere no final e novamente não realiza ordenamento nenhum. A tentativa de inserção foi o número 9:
[1, 2, 3, 5, 6, 7, 4, 8, 10, 9]

Obs: Não consegui entender como funciona o ordenamento.

Essa questão é muito facil. A classe PriorityQueue utiliza uma estrutura da dados chamada Heap. Que é uma estrutura de árvore binária (sem a ordenação da arvore binaria) que mantém o elemento de maior prioridade na raiz. basta dar uma lida nessa estrutura de dados e vc’s vao entender.

T+

A unica garantia que um heap da é a seguinte:

elemtento X > elemento 2X
element X > elemento 2 X

entao o primeiro elemento sera maior que o 2o eo o 3o.
o 2o elemento sera maior que o 4o e o 5o, mas nao necessariamente maior que o 3o!
o 3o ser maior que o 6o e que o 7o.

assim por diante…

e quando voce remove/insere elementos, ele se rearranja rapidamente para manter essa propriedade