W implementacji kolejki priorytetów Java usuń przy metodzie, dlaczego przesyła się po odłożeniu?

Question

Czytałem API kolekcji Java, priorytetową część kolejki, która jest realizowana przez Josh Blocha i Douga Lea, pracę dwóch maestrów.

Java PriorityQueue jest zaimplementowana z stertą tablicy.

fragmentów kodu są tu od PriorityQueue.java, Linia 600:

/** 
* Removes the ith element from queue. 
* 
* Normally this method leaves the elements at up to i-1, 
* inclusive, untouched. Under these circumstances, it returns 
* null. Occasionally, in order to maintain the heap invariant, 
* it must swap a later element of the list with one earlier than 
* i. Under these circumstances, this method returns the element 
* that was previously at the end of the list and is now at some 
* position before i. This fact is used by iterator.remove so as to 
* avoid missing traversing elements. 
*/ 

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); 
      //the code I am asking is below: 
      if (queue[i] == moved) { 
       siftUp(i, moved); 
       if (queue[i] != moved) 
        return moved; 
      } 
     } 
     return null; 
    } 

Co ja zastanawiałem się, że element przeniesiony, który kiedyś na dnie stosu, powinna być duża jeden sub drzewa z i. Metoda siftDown jest uzasadniona, po siftDown najmniejszy z poddrzewa zostanie podniesiony do pozycji i.

Pytanie brzmi, czy i się nie zmienia, to znaczy przeniesiony nadal istnieje po siftDown, wydaje mi się, że drzewo sub już heapified, to nie musi być siftUp ponownie.

Dlaczego Josh podnosi je ponownie na sam szczyt?

Mam nadzieję, że ci, którzy przeczytali kod, pomogą!

Answer 1

Problem polega na tym, że przeniesiony element (pozycja pod numerem queue[size-1]) może nie znajdować się w tym samym poddrzewie, co element, który został usunięty. Rozważmy tę kupę:

 0 
    4  1 
5 6 2 3 

Teraz jeśli usunąć węzeł 5 masz:

 0 
    4  1 
    6 2 3 

wziąć ostatni węzeł w stercie, 3, i umieścić go w miejscu, gdzie 5 było:

 0 
    4  1 
3 6 2 

Przesiewasz 3 w dół, ale to już liść. Jest potencjalnie nie na miejscu. Musisz przesiać go, aby uzyskać:

 0 
    3  1 
4 6 2