Sorgt die remove-Methode von PriorityQueue für eine Neuanordnung des Heapspeichers?

Question

Wenn die Methode remove in einem PriorityQueue Objekt in Java aufgerufen wird, wird der Kopf des Heap entfernt. Um das neue minimale Element an die Spitze zu setzen, werden irgendwelche Sortieroperationen auf dem Rest des Heaps durchgeführt? Wird zum Beispiel die compareTo-Methode aufgerufen, wenn remove aufgerufen wird?

Entschuldigung, wenn dies in der Dokumentation ist, kann ich es nirgends finden. Danke im Voraus.

Answer 1

Die PriorityQueue ist als eine ausgeglichene binäre Heap implementiert als ein Array implementiert. Wenn ein Element entfernt wird, muss sich der Heap neu anordnen, um die Reihenfolge des Heapspeichers beizubehalten.

Der Beweis ist in den Kommentaren

/** 
* 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; 

Auch in der Klasse javadoc

Implementierung Hinweis: Diese Implementierung stellt O (log (n)) Zeit für die Enqueing und dequeing Methoden (anbieten, abstimmen, entfernen() und hinzufügen); lineare Zeit für das Entfernen (Object) und enthält (Object) Methoden; und Konstante Zeit für die Abrufmethoden (Peek, Element und Größe).

Für remove(), zum Beispiel, entfernen Sie die Wurzel des Heap. Du nimmst das letzte Element, d. rechten Blatt auf der letzten Ebene des Binärbaums, und setzen Sie es als root und machen Sie sieben, bis es seinen Platz findet (basierend auf Comparator). Das dauert im schlimmsten Fall O(log n) Zeit.

Answer 2

Kommt drauf an. Wenn Sie remove das letzte Element in dem Array, das die PriorityQueue unterstützt, werden, wird kein Umsortieren durchgeführt. Wenn Sie remove ein anderes Element, wird es seine Elemente neu anordnen (siftUp und 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; 
}