在Java Priority Queue實現方法中刪除，爲什麼篩選後篩選出來？

我一直在閱讀由Josh Bloch和Doug Lea兩位大師的作品實現的Java收集API，優先級隊列部分。使用數組堆實現Java PriorityQueue。在Java Priority Queue實現方法中刪除，爲什麼篩選後篩選出來？

的代碼片段都在這裏，從PriorityQueue.java，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; 
    }

什麼我不知道的是，移動的元素，它曾經是在堆的底部，應該是一個大的從i的子樹。 siftDown方法是合理的，在siftDown之後，最小的子樹將被解除到i的位置。

的問題是，如果i沒有改變，即感動還是有的siftDown後，在我看來，該子樹已經heapified，它並不需要再次siftUp。

爲什麼喬希再次將它們提升到頂端？

希望讀過代碼的人幫忙！

來源

2016-08-01 stayclean

問題是移動的項目（queue[size-1]處的項目）可能與刪除的項目不在同一子樹中。考慮這個堆：

 0 
    4  1 
5 6 2 3

現在，如果你刪除節點5您有：

 0 
    4  1 
    6 2 3

你拿的最後一個節點在堆中，3，並把它在5是地方：

 0 
    4  1 
3 6 2

你篩選出3個，但它已經是一片葉子。它可能不合適。你必須篩選它以獲得：

 0 
    3  1 
4 6 2

來源

2016-08-02 22:26:51

謝謝吉姆！堆的一側的大元素可能不會像同一層中的其他元素一樣大。我認爲你描述的情景可能只發生在葉級。如果siftDown沒有改變位置並且它有孩子，那麼siftUp似乎是重新排列的。這是對的嗎？希望澄清。 – stayclean

添加到以前的評論，特別是在基於數組的堆實現中，唯一的情況是葉子。 – stayclean

@stayclean：這不限於葉級。在一個更大的堆中，它可能發生在樹葉之上的許多層次。你應該可以用比我的例子更深一層的堆來構建這樣一個案例。 –

在Java Priority Queue實現方法中刪除，爲什麼篩選後篩選出來？

回答

相關問題