Menu
I have been reading Java collection API, the priority queue part, which is implemented by Josh Bloch and Doug Lea, the two maestros' work.
The Java PriorityQueue is implemented with array heap.
The code snippets are here , 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;
}
What I am wondered is that, the moved element, which used to be at the bottom of the heap, should be a large one of the sub tree from i. The siftDown method is reasonable, after a siftDown, the smallest of the subtree will be lifted to the position i.
The question is, if the i does not change, i.e. the moved is still there after siftDown, it seems to me that the sub tree has already been heapified, it does not need to be siftUp again.
Why Josh lift them up again to the top?
Hope those who has read the code helps!
339
We can use heaps to implement the priority queue. It will take O(log N) time to insert and delete each element in the priority queue.
2) Deletion in a Priority Queue And it will remove the element which has maximum priority first. Thus, you remove the root node from the queue.
The remove() method of PriorityQueue class of java. util package is used to remove a particular element from a PriorityQueue.
Priority Queues Elements are retrieved according to their priority. Priority 1 denotes the most urgent priority. Each removal extracts the minimum element. When you retrieve an item from a priority queue, you always get the most urgent one.
The problem is that the moved item (the item at queue[size-1]) might not be in the same subtree as the item that was removed. Consider this heap:
0
4 1
5 6 2 3
Now if you remove the node 5 you have:
0
4 1
6 2 3
You take the last node in the heap, 3, and put it in the place where 5 was:
0
4 1
3 6 2
You sift 3 down, but it's already a leaf. It's potentially out of place. You have to sift it up to obtain:
0
3 1
4 6 2
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
