Java priorityQueue update problem

Question

(sorry for my bad english) I am writing a Dijkstra algoritm implementation and I need to use the priority queue. I am using PriorityQueue as defined in the Java SE 6 platform. Is there a method, for example, the Q.update () method in the Java Platform SE 5, that rebuilds the priority queue in case of changing the priorities of its elements from the moment they are installed? (I have a problem with rest and Q.poll ()) I need the update to accept O (log n)

Answer 1

Updating the priority of an element already in the priority queue is an important operation, and the priority queue that does not offer this operation is more or less useless.

The implementation of the priority queue, which allows updating an already inserted value at O ​​(log n) time , is as follows:

/** * PriorityQueue with updatePriority and item concept. * Makes use of a min heap. * * @author Chris Stamm * @version 6.10.2013 */ import java.util.*; public class PQueue<E extends Comparable<E>> { public static class PQItem<E extends Comparable<E>> implements Comparable<PQItem<E>> { private E m_data; private int m_index; public PQItem(E data, int index) { m_data = data; m_index = index; } public int compareTo(PQItem<E> item) { return m_data.compareTo(item.m_data); } public E getData() { return m_data; } public void setIndex(int index) { m_index = index; } public int getIndex() { return m_index; } } private ArrayList<PQItem<E>> m_array; public PQueue() { m_array = new ArrayList<PQItem<E>>(); } /** * O(n) */ public PQueue(Collection<? extends E> c) { m_array = new ArrayList<PQItem<E>>(c.size()); // copy elements int j = 0; for(E e: c) { m_array.add(new PQItem(e, j++)); } // create heap final int s = m_array.size(); int l2 = s/2 - 1; for (int i = l2; i >= 0; i--) { siftDown(i); } } public int size() { return m_array.size(); } public boolean isEmpty() { return m_array.isEmpty(); } /** * O(log n) */ public PQItem<E> add(E data) { int s = size(); PQItem<E> item = new PQItem(data, s); m_array.add(item); siftUp(s); return item; } /** * O(log n) */ public E removeFirst() { int size = size(); if (size == 0) return null; if (size == 1) return m_array.remove(0).getData(); int last = size - 1; // swap a[first] with a[last] PQItem<E> t = m_array.get(0); E data = t.getData(); set(0, m_array.get(last)); set(last, t); // remove last m_array.remove(last); // heapify siftDown(0); return data; } public void clear() { m_array.clear(); } public PQItem<E> getItem(int i) { return (i >= 0 && i < size()) ? m_array.get(i) : null; } public PQItem<E> getFirstItem() { return getItem(0); } public PQItem<E> getNextItem(PQItem<E> item) { if (item == null) return null; int index = item.getIndex() + 1; return (index < size()) ? m_array.get(index) : null; } /** * O(log n) */ public void updatePriority(PQItem<E> item) { int pos = item.getIndex(); if (pos > 0) { // check heap condition at parent int par = (pos - 1)/2; if (m_array.get(par).compareTo(m_array.get(pos)) > 0) { siftUp(pos); return; } } int son = pos*2 + 1; if (son < size()) { // check heap condition at son if (m_array.get(pos).compareTo(m_array.get(son)) > 0) { siftDown(pos); } } } private int set(int pos, PQItem<E> item) { int oldIndex = item.getIndex(); item.setIndex(pos); m_array.set(pos, item); return oldIndex; } /** * sift down at position pos. * O(log n) */ private void siftDown(int pos) { final int end = size() - 1; int son = pos*2 + 1; while (son <= end) { // son ist der linke Sohn if (son < end) { // pos hat auch einen rechten Sohn if (m_array.get(son).compareTo(m_array.get(son + 1)) > 0) son++; } // son ist der grössere Sohn if (m_array.get(pos).compareTo(m_array.get(son)) > 0) { // swap a[pos] with a[son] PQItem<E> t = m_array.get(pos); set(pos, m_array.get(son)); set(son, t); pos = son; son = 2*pos + 1; } else { return; } } } /** * sift up at position pos * O(log n) */ private void siftUp(int pos) { int par = (pos - 1)/2; // parent while(par >= 0) { if (m_array.get(par).compareTo(m_array.get(pos)) > 0) { // swap a[par] with a[pos] PQItem<E> t = m_array.get(par); set(par, m_array.get(pos)); set(pos, t); pos = par; par = (pos - 1)/2; } else { return; } } } } 

And here are three small examples of using the priority queue.

 static void showMinHeap() { Integer[] values = { 7, 9, 6, 3, 5, 1, 2, 8, 4, 0}; PQueue<Integer> pq = new PQueue<Integer>(Arrays.asList(values)); int lev = 1, i = 0; PQueue.PQItem<Integer> item = pq.getFirstItem(); while(item != null) { if (i == lev) { System.out.println(); lev <<= 1; i = 0; } System.out.print(item.getData()); System.out.print(' '); i++; item = pq.getNextItem(item); } System.out.println(); } static void heapSort() { Integer[] values = { 7, 9, 6, 3, 5, 1, 2, 8, 4, 0}; PQueue<Integer> pq = new PQueue<Integer>(Arrays.asList(values)); for(int i=0; i < values.length; i++) { System.out.print(pq.removeFirst()); System.out.print(' '); } System.out.println(); } static void testNodes() { class Node implements Comparable<Node> { private int m_key; public Node(int k) { m_key = k; } public void updateKey() { m_key *= 2; } public int compareTo(Node v) { return (m_key == v.m_key) ? 0 : (m_key < v.m_key) ? -1 : 1; } public String toString() { return String.valueOf(m_key); } } PQueue<Node> pq= new PQueue<Node>(); Random rand = new Random(7777); final int size = 20; for (int i = 0; i < size; i++) { Node v = new Node(rand.nextInt(size)); pq.add(v); } for (int i = 0; i < size; i++) { // change key and update priority PQueue.PQItem<Node> item = pq.getItem(rand.nextInt(pq.size())); item.getData().updateKey(); pq.updatePriority(item); // remove and show first System.out.println(pq.removeFirst()); } System.out.println(); } 

Answer 2

No, with PriorityQueue , there is no way to reload items while they are in the queue.

This is the usual optimization for heaps. Although the time complexity of removing the top of the heap and putting the (updated) element back into the heap is in the same order, it takes about half the time to notify the heap that the top element is updated and you may need to move down to the heap.