我一直在阅读Java集合API,这是优先级队列部分,由两位大师的作品Josh Bloch和Doug Lea实现.
Java 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 …