The Java implementation of the queue priority, remove the method, why it is sifted after sifting down?

Question

I read the API-interface the Java collection, part of the priority queue, which is implemented by Josh Bloch and Doug Lee, two works of the maestro.

Java PriorityQueue implemented with a heap array.

The following code fragments are shown from PriorityQueue.java , line 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; } the list with one earlier than /** * 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; } element /** * 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; } to /** * 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; } last element /** * 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; } s]; /** * 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; } : /** * 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; } ) { /** * 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 wonder what moved the element that used to be at the bottom of the heap should be large from the subtree of i . Method siftDown reasonable, after a siftDown smallest of subtrees will be raised to the position i .

The question is, if i is not changed, i.e., moved still exists after siftDown , it seems to me that the subtree has been created, it does not have to be siftUp again

Why Josh lifts them back to the top?

I hope that those who read the code can help!

Answer 1

The problem is that the moved element (an element in the queue[size-1] ) can not be in the same subtree as the content item that has been deleted. Consider this bunch:

  0 4 1 5 6 2 3 

Now, if you remove node 5, you:

  0 4 1 6 2 3 

You take the last node in a heap, 3, and place it in a place where it was 5:

  0 4 1 3 6 2 

You sift 3 down, but this is already a leaf. This potentially inappropriate. You must sift it to get:

  0 3 1 4 6 2