 <p>That's right. <code>PriorityQueue</code> of Java does not offer a method to update priority and it seems that deletion is taking linear time since it does not store objects as keys, as <code>Map</code> does. It in fact accepts same object multiple times.</p> <p>I also wanted to make PQ offering update operation. Here is the sample code using generics. Any class that is Comparable can be used with it.</p> <pre><code>class PriorityQueue&lt;E extends Comparable&lt;E&gt;&gt; { List&lt;E&gt; heap = new ArrayList&lt;E&gt;(); Map&lt;E, Integer&gt; map = new HashMap&lt;E, Integer&gt;(); void insert(E e) { heap.add(e); map.put(e, heap.size() - 1); bubbleUp(heap.size() - 1); } E deleteMax() { if(heap.size() == 0) return null; E result = heap.remove(0); map.remove(result); heapify(0); return result; } E getMin() { if(heap.size() == 0) return null; return heap.get(0); } void update(E oldObject, E newObject) { int index = map.get(oldObject); heap.set(index, newObject); bubbleUp(index); } private void bubbleUp(int cur) { while(cur &gt; 0 &amp;&amp; heap.get(parent(cur)).compareTo(heap.get(cur)) &lt; 0) { swap(cur, parent(cur)); cur = parent(cur); } } private void swap(int i, int j) { map.put(heap.get(i), map.get(heap.get(j))); map.put(heap.get(j), map.get(heap.get(i))); E temp = heap.get(i); heap.set(i, heap.get(j)); heap.set(j, temp); } private void heapify(int index) { if(left(index) &gt;= heap.size()) return; int bigIndex = index; if(heap.get(bigIndex).compareTo(heap.get(left(index))) &lt; 0) bigIndex = left(index); if(right(index) &lt; heap.size() &amp;&amp; heap.get(bigIndex).compareTo(heap.get(right(index))) &lt; 0) bigIndex = right(index); if(bigIndex != index) { swap(bigIndex, index); heapify(bigIndex); } } private int parent(int i) { return (i - 1) / 2; } private int left(int i) { return 2*i + 1; } private int right(int i) { return 2*i + 2; } } </code></pre> <p>Here while updating, I am only increasing the priority (for my implementation) and it is using MaxHeap, so I am doing bubbleUp. One may need to heapify based on requirement.</p>