Il metodo di rimozione di PriorityQueue riorganizza l'heap?

Question

Quando il metodo remove viene chiamato su un oggetto PriorityQueue in java, viene rimossa la testa dell'heap. Per mettere il nuovo elemento minimo in testa, ci sono operazioni di smistamento fatte sul resto dell'heap? Ad esempio, è il metodo compareTo chiamato quando viene chiamato remove?

Ci scusiamo se questo è nel documento, non riesco a trovarlo da nessuna parte. Grazie in anticipo.

Answer 1

Il PriorityQueue viene implementato come heap binario bilanciato implementato come array. Quando un elemento viene rimosso, l'heap deve riordinare se stesso per mantenere l'ordine dell'heap.

La prova è nei commenti

/** 
* Priority queue represented as a balanced binary heap: the two 
* children of queue[n] are queue[2*n+1] and queue[2*(n+1)]. The 
* priority queue is ordered by comparator, or by the elements' 
* natural ordering, if comparator is null: For each node n in the 
* heap and each descendant d of n, n <= d. The element with the 
* lowest value is in queue[0], assuming the queue is nonempty. 
*/ 
private transient Object[] queue; 

Anche nel javadoc classe

nota implementazione: questa implementazione fornisce O (log (n)) per l'Enqueing e metodi dequeing (offrire, sondare, rimuovere() e aggiungere); tempo lineare per il metodo remove (Object) e contiene (Object); e tempo costante per i metodi di recupero (peek, elemento e dimensione).

Per remove(), ad esempio, si rimuove la radice dell'heap. Prendi l'ultimo elemento, cioè. all'estrema destra all'ultimo livello dell'albero binario e posizionalo come root e fai lo svergolamento fino a quando non trova il suo posto (basato su Comparator). Nel peggiore dei casi è il momento O(log n).

Answer 2

Dipende. Se si è remove l'ultimo elemento dell'array che supporta lo PriorityQueue, non verrà eseguito alcun ricorso. Se remove qualsiasi altro elemento, sarà riordinare i suoi elementi (siftUp e siftDown):

public boolean remove(Object o) { 
    int i = indexOf(o); 
    if (i == -1) 
     return false; 
    else { 
     removeAt(i); 
     return true; 
    } 
} 

private E removeAt(int i) { 
    assert i >= 0 && i < size; 
    modCount++; 
    int s = --size; 
    if (s == i) // removed last element 
     queue[i] = null; 
    else { 
     E moved = (E) queue[s]; 
     queue[s] = null; 
     siftDown(i, moved); 
     if (queue[i] == moved) { 
      siftUp(i, moved); 
      if (queue[i] != moved) 
       return moved; 
     } 
    } 
    return null; 
}