जावा प्राथमिकता कतार कार्यान्वयन विधि में हटा दें, यह एक झुकाव के बाद क्यों उछालता है?

Question

मैं जावा संग्रह एपीआई, प्राथमिकता कतार भाग पढ़ रहा हूं, जो कि दो मास्टर्स के काम, जोश ब्लोच और डौग ली द्वारा कार्यान्वित किया गया है।

जावा PriorityQueue सरणी ढेर के साथ लागू किया गया है।

कोड के टुकड़े यहाँ हैं, 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 फिर से होने की जरूरत नहीं है।

क्यों जोश ने उन्हें शीर्ष पर फिर से उठाया?

उम्मीद है कि कोड पढ़ने वाले लोगों की मदद करता है!

Answer 1

समस्या यह है कि स्थानांतरित आइटम (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