Updating Java PriorityQueue when its elements change priority
JDK Code - Default, it's MinHeap.
poll or peek will return null(not throw exception)if there is no more element.
http://www.cnblogs.com/tstd/p/5125949.html
You have to remove and re-insert, as the queue works by putting new elements in the appropriate position when they are inserted. This is much faster than the alternative of finding the highest-priority element every time you pull out of the queue. The drawback is that you cannot change the priority after the element has been inserted. A TreeMap has the same limitation (as does a HashMap, which also breaks when the hashcode of its elements changes after insertion).
JDK Code - Default, it's MinHeap.
poll or peek will return null(not throw exception)if there is no more element.
public class PriorityQueue<E> extends AbstractQueue<E>
implements java.io.Serializable {
private static final int DEFAULT_INITIAL_CAPACITY = 11;
/**
* Priority queue represented as a balanced binary heap: the two
* children of queue[n] are queue[2*n+1] and queue[2*(n+1)]. The
* priority queue is ordered by comparator, or by the elements'
* natural ordering, if comparator is null: For each node n in the
* heap and each descendant d of n, n <= d. The element with the
* lowest value is in queue[0], assuming the queue is nonempty.
*/
transient Object[] queue; // non-private to simplify nested class access
* The maximum size of array to allocate.
* Some VMs reserve some header words in an array.
* Attempts to allocate larger arrays may result in
* OutOfMemoryError: Requested array size exceeds VM limit
*/
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
public boolean offer(E e) {
if (e == null)
throw new NullPointerException();
modCount++;
int i = size;
if (i >= queue.length)
grow(i + 1);
size = i + 1;
if (i == 0)
queue[0] = e;
else
siftUp(i, e);
return true;
}
private void siftUp(int k, E x) {
if (comparator != null)
siftUpUsingComparator(k, x);
else
siftUpComparable(k, x);
}
private void siftUpComparable(int k, E x) {
Comparable<? super E> key = (Comparable<? super E>) x;
while (k > 0) {
int parent = (k - 1) >>> 1;
Object e = queue[parent];
if (key.compareTo((E) e) >= 0)
break;
queue[k] = e;
k = parent;
}
queue[k] = key;
}
private void siftUpUsingComparator(int k, E x) {
while (k > 0) {
int parent = (k - 1) >>> 1;
Object e = queue[parent];
if (comparator.compare(x, (E) e) >= 0)
break;
queue[k] = e;
k = parent;
}
queue[k] = x;
}
public E peek() {
return (size == 0) ? null : (E) queue[0];
}
public E poll() {
if (size == 0)
return null;
int s = --size;
modCount++;
E result = (E) queue[0];
E x = (E) queue[s];
queue[s] = null;
if (s != 0)
siftDown(0, x);
return result;
}
private void siftDown(int k, E x) {
if (comparator != null)
siftDownUsingComparator(k, x);
else
siftDownComparable(k, x);
}
@SuppressWarnings("unchecked")
private void siftDownComparable(int k, E x) {
Comparable<? super E> key = (Comparable<? super E>)x;
int half = size >>> 1; // loop while a non-leaf
while (k < half) {
int child = (k << 1) + 1; // assume left child is least
Object c = queue[child];
int right = child + 1;
if (right < size &&
((Comparable<? super E>) c).compareTo((E) queue[right]) > 0)
c = queue[child = right];
if (key.compareTo((E) c) <= 0)
break;
queue[k] = c;
k = child;
}
queue[k] = key;
}
@SuppressWarnings("unchecked")
private void siftDownUsingComparator(int k, E x) {
int half = size >>> 1;
while (k < half) {
int child = (k << 1) + 1;
Object c = queue[child];
int right = child + 1;
if (right < size &&
comparator.compare((E) c, (E) queue[right]) > 0)
c = queue[child = right];
if (comparator.compare(x, (E) c) <= 0)
break;
queue[k] = c;
k = child;
}
queue[k] = x;
}
/**
* Establishes the heap invariant (described above) in the entire tree,
* assuming nothing about the order of the elements prior to the call.
*/
private void heapify() {
for (int i = (size >>> 1) - 1; i >= 0; i--)
siftDown(i, (E) queue[i]);
}
private void writeObject(java.io.ObjectOutputStream s)
throws java.io.IOException {
// Write out element count, and any hidden stuff
s.defaultWriteObject();
// Write out array length, for compatibility with 1.5 version
s.writeInt(Math.max(2, size + 1));
// Write out all elements in the "proper order".
for (int i = 0; i < size; i++)
s.writeObject(queue[i]);
}
private void readObject(java.io.ObjectInputStream s)
throws java.io.IOException, ClassNotFoundException {
// Read in size, and any hidden stuff
s.defaultReadObject();
// Read in (and discard) array length
s.readInt();
queue = new Object[size];
// Read in all elements.
for (int i = 0; i < size; i++)
queue[i] = s.readObject();
// Elements are guaranteed to be in "proper order", but the
// spec has never explained what that might be.
heapify();
}
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);
if (queue[i] == moved) {
siftUp(i, moved);
if (queue[i] != moved)
return moved;
}
}
return null;
}
private int indexOf(Object o) {
if (o != null) {
for (int i = 0; i < size; i++)
if (o.equals(queue[i]))
return i;
}
return -1;
}
private void grow(int minCapacity) {
int oldCapacity = queue.length;
// Double size if small; else grow by 50%
int newCapacity = oldCapacity + ((oldCapacity < 64) ?
(oldCapacity + 2) :
(oldCapacity >> 1));
// overflow-conscious code
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
queue = Arrays.copyOf(queue, newCapacity);
}
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}
public PriorityQueue(Collection<? extends E> c) {
if (c instanceof SortedSet<?>) {
SortedSet<? extends E> ss = (SortedSet<? extends E>) c;
this.comparator = (Comparator<? super E>) ss.comparator();
initElementsFromCollection(ss);
}
else if (c instanceof PriorityQueue<?>) {
PriorityQueue<? extends E> pq = (PriorityQueue<? extends E>) c;
this.comparator = (Comparator<? super E>) pq.comparator();
initFromPriorityQueue(pq);
}
else {
this.comparator = null;
initFromCollection(c);
}
}
private void initFromPriorityQueue(PriorityQueue<? extends E> c) {
if (c.getClass() == PriorityQueue.class) {
this.queue = c.toArray();
this.size = c.size();
} else {
initFromCollection(c);
}
}
private void initElementsFromCollection(Collection<? extends E> c) {
Object[] a = c.toArray();
// If c.toArray incorrectly doesn't return Object[], copy it.
if (a.getClass() != Object[].class)
a = Arrays.copyOf(a, a.length, Object[].class);
int len = a.length;
if (len == 1 || this.comparator != null)
for (int i = 0; i < len; i++)
if (a[i] == null)
throw new NullPointerException();
this.queue = a;
this.size = a.length;
}
private void initFromCollection(Collection<? extends E> c) {
initElementsFromCollection(c);
heapify();
}
}http://www.cnblogs.com/tstd/p/5125949.html
为了维护这个特点，二叉堆在添加元素的时候，需要一个"上移"的动作，什么是"上移"呢，我们继续用图来说明。
11 public boolean offer(E e) { 12 // 如果元素e为空，则排除空指针异常 13 if (e == null) 14 throw new NullPointerException(); 15 // 修改版本+1 16 modCount++; 17 // 记录当前队列中元素的个数 18 int i = size ; 19 // 如果当前元素个数大于等于队列底层数组的长度，则进行扩容 20 if (i >= queue .length) 21 grow(i + 1); 22 // 元素个数+1 23 size = i + 1; 24 // 如果队列中没有元素，则将元素e直接添加至根（数组小标0的位置） 25 if (i == 0) 26 queue[0] = e; 27 // 否则调用siftUp方法，将元素添加到尾部，进行上移判断 28 else 29 siftUp(i, e); 30 return true; 31 }
4 private void siftUp(int k, E x) { 5 // 如果比较器comparator不为空，则调用siftUpUsingComparator方法进行上移操作 6 if (comparator != null) 7 siftUpUsingComparator(k, x); 8 // 如果比较器comparator为空，则调用siftUpComparable方法进行上移操作 9 else 10 siftUpComparable(k, x); 11 } 12 13 private void siftUpComparable(int k, E x) { 14 // 比较器comparator为空，需要插入的元素实现Comparable接口，用于比较大小 15 Comparable<? super E> key = (Comparable<? super E>) x; 16 // k>0表示判断k不是根的情况下，也就是元素x有父节点 17 while (k > 0) { 18 // 计算元素x的父节点位置[(n-1)/2] 19 int parent = (k - 1) >>> 1; 20 // 取出x的父亲e 21 Object e = queue[parent]; 22 // 如果新增的元素k比其父亲e大，则不需要"上移"，跳出循环结束 23 if (key.compareTo((E) e) >= 0) 24 break; 25 // x比父亲小，则需要进行"上移" 26 // 交换元素x和父亲e的位置 27 queue[k] = e; 28 // 将新插入元素的位置k指向父亲的位置，进行下一层循环 29 k = parent; 30 } 31 // 找到新增元素x的合适位置k之后进行赋值 32 queue[k] = key; 33 } 34 35 // 这个方法和上面的操作一样，不多说了 36 private void siftUpUsingComparator(int k, E x) { 37 while (k > 0) { 38 int parent = (k - 1) >>> 1; 39 Object e = queue[parent]; 40 if (comparator .compare(x, (E) e) >= 0) 41 break; 42 queue[k] = e; 43 k = parent; 44 } 45 queue[k] = x; 46 }
对于二叉堆的出队操作，出队永远是要删除根元素，也就是最小的元素，要删除根元素，就要找一个替代者移动到根位置，相对于被删除的元素来说就是"下移"。
4 public E remove() { 5 E x = poll(); 6 if (x != null) 7 return x; 8 else 9 throw new NoSuchElementException(); 10 } 11 12 /** 13 * 删除并返回队头的元素，如果队列为空则返回null 14 */ 15 public E poll() { 16 // 队列为空，返回null 17 if (size == 0) 18 return null; 19 // 队列元素个数-1 20 int s = --size ; 21 // 修改版本+1 22 modCount++; 23 // 队头的元素 24 E result = (E) queue[0]; 25 // 队尾的元素 26 E x = (E) queue[s]; 27 // 先将队尾赋值为null 28 queue[s] = null; 29 // 如果队列中不止队尾一个元素，则调用siftDown方法进行"下移"操作 30 if (s != 0) 31 siftDown(0, x); 32 return result; 33 } 34 35 /** 36 * 上移，x表示队尾的元素，k表示被删除元素在数组的位置 37 */ 38 private void siftDown(int k, E x) { 39 // 如果比较器comparator不为空，则调用siftDownUsingComparator方法进行下移操作 40 if (comparator != null) 41 siftDownUsingComparator(k, x); 42 // 比较器comparator为空，则调用siftDownComparable方法进行下移操作 43 else 44 siftDownComparable(k, x); 45 } 46 47 private void siftDownComparable(int k, E x) { 48 // 比较器comparator为空，需要插入的元素实现Comparable接口，用于比较大小 49 Comparable<? super E> key = (Comparable<? super E>)x; 50 // 通过size/2找到一个没有叶子节点的元素 51 int half = size >>> 1; // loop while a non-leaf 52 // 比较位置k和half，如果k小于half，则k位置的元素就不是叶子节点 53 while (k < half) { 54 // 找到根元素的左孩子的位置[2n+1] 55 int child = (k << 1) + 1; // assume left child is least 56 // 左孩子的元素 57 Object c = queue[child]; 58 // 找到根元素的右孩子的位置[2(n+1)] 59 int right = child + 1; 60 // 如果左孩子大于右孩子，则将c复制为右孩子的值，这里也就是找出左右孩子哪个最小 61 if (right < size && 62 ((Comparable<? super E>) c).compareTo((E) queue [right]) > 0) 63 c = queue[child = right]; 64 // 如果队尾元素比根元素孩子都要小，则不需"下移"，结束 65 if (key.compareTo((E) c) <= 0) 66 break; 67 // 队尾元素比根元素孩子都大，则需要"下移" 68 // 交换跟元素和孩子c的位置 69 queue[k] = c; 70 // 将根元素位置k指向最小孩子的位置，进入下层循环 71 k = child; 72 } 73 // 找到队尾元素x的合适位置k之后进行赋值 74 queue[k] = key; 75 } 76 77 // 这个方法和上面的操作一样，不多说了 78 private void siftDownUsingComparator(int k, E x) { 79 int half = size >>> 1; 80 while (k < half) { 81 int child = (k << 1) + 1; 82 Object c = queue[child]; 83 int right = child + 1; 84 if (right < size && 85 comparator.compare((E) c, (E) queue [right]) > 0) 86 c = queue[child = right]; 87 if (comparator .compare(x, (E) c) <= 0) 88 break; 89 queue[k] = c; 90 k = child; 91 } 92 queue[k] = x; 93 }
int a = [7, 6, 5, 12, 10, 3, 1, 11, 15, 4 ];我们观察下用数组a建成的二叉堆，很明显，对于叶子节点4、15、11、1、3来说，它们已经是一个合法的堆。所以只要最后一个节点的父节点，也就是最后一个非叶子节点a[4]=10开始调整，然后依次调整a[3]=12，a[2]=5，a[1]=6，a[0]=7，分别对这几个节点做一次"下移"操作就可以完成了堆的构造。ok，我们还是用图解来分析下这个过程。
5 private void heapify() { 6 for (int i = (size >>> 1) - 1; i >= 0; i--) 7 siftDown(i, (E) queue[i]); 8 }
1 private void heapify() { 2 for (int i = (size >>> 1) - 1; i >= 0; i--) 3 siftDown(i, (E) queue[i]); 4 }
int i = (size >>> 1) - 1，这行代码是为了找寻最后一个非叶子节点，然后倒序进行"下移"siftDown操作，是不是很显然了。
