5

I have a PriorityQueue containing references to some objects. When I initially insert the elements into the priority queue the ordering is maintained by the data structure. Now after a remove operation I update some of the references which are being held by the priority queue. Ideally this requires a reheapify operation on the priority queue but as is obvious since I am modifying selected references externally a reheapify cannot be triggered. So what is the best way to ensure that I am able to get the advantage of a heap like fast extract max in the presence of modifications to arbitrary elements inside the queue? I see I need a better data structure?

To be more specific I need an implementation of something like a Fibonacci heap in Java. http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm Is that available?

James Montagne
  • 77,516
  • 14
  • 110
  • 130
Rohit Banga
  • 18,458
  • 31
  • 113
  • 191
  • I have an implementation of a Fibonacci heap in Java if you're interested. It's available online at http://www.keithschwarz.com/interesting/code/?dir=fibonacci-heap . Hope it helps! – templatetypedef Dec 29 '11 at 03:43
  • Even fibonacci heaps aren't resilient in the face of out-of-band changes to the weights of elements. I think you need to remove an element before you modify it and reinsert it afterwards. – Mike Samuel Dec 29 '11 at 04:46
  • removing an arbitrary element from the heap will require O(n) heap construction I guess. – Rohit Banga Dec 29 '11 at 05:17
  • The problem I guess is that the PriorityQueue provides me a linear time remove operation. If the data structure was transparent enough I could externally maintain the index of all elements in the priority queue so I could implement the DECREASE-KEY operation in O(lg V) time. Does anyone see any other data structure that can help me achieve this? – Rohit Banga Dec 29 '11 at 15:35
  • Does noone have an idea how we could get the efficient implementation using Java Collections API? – Rohit Banga Jan 05 '12 at 15:54
  • 1
    See also http://stackoverflow.com/questions/1871253/updating-java-priorityqueue-when-its-elements-change-priority – Raedwald Mar 20 '15 at 13:03

2 Answers2

2

You can use your own tree that allows duplicate elements instead of heap. Easier though, you can use TreeMap<PriorityKey, LinkedHashSet<Value>>. All operations are O(log priorityType):

  • adding is get(priority).add(value), if get returns null, put(priority, new LinkedHashSet())
  • removing an arbitrary element is similar, except needs to remove the priority out of the map if the Set is empty.
  • poll() is

--

Entry<PriorityKey, LinkedHashSet<Value>> e = map.firstEntry(); 
if (e==null) return null; 
Iterator<Value> i = e.getValue().iterator(); 
Value v = i.next(); //must always have at least one element.
i.remove(); 
if (!i.hasNext()) map.remove(e.getKey());
return v;

Still if you need to change the priority you have to remove and add the element.

bestsss
  • 11,796
  • 3
  • 53
  • 63
  • OK ... so I would say that the PriorityQueue in Java neither implements the DecreaseKey operation nor provides a way for the user to implement it efficiently. – Rohit Banga Feb 05 '12 at 20:04
  • @iamrohitbanga, finding a key in heap is O(n), then you can remove/add which is (log N), again if you need to access a random element in the queue you'd be better off w/ a tree. – bestsss Feb 05 '12 at 21:13
1

Maybe a NavigableMap would suit your needs : easy identification of the "highest" or "lowest" element, fast insertion and access time, and you could update values easily.

http://docs.oracle.com/javase/7/docs/api/java/util/NavigableMap.html

TreeMap implements NavigableMap, and therefore provides the firstEntry/lastEntry methods, and many more.

Olivier Croisier
  • 6,139
  • 25
  • 34
  • you cant have duplicate elements in the map and it has to be sorted by priority. the solution of using a tree(map) involves mapping priority->collection. (what i posted) – bestsss Feb 08 '12 at 09:55