Geek Answers Handbook

Restore java.util.PriorityQueue after updating items

I have a PriorityQueue containing references to some objects. When I first insert items into the priority queue, ordering is supported by the data structure. Now, after the delete operation, I update some links that are stored in the priority queue. Ideally, this requires a reheapify operation in the priority queue, but, as is obvious, since I am changing the selected links from the outside, a restart cannot be called. So, what is the best way to ensure that I can take advantage of the heap, for example, quick extract max when there are changes to arbitrary elements within 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 this available?

+5
source share
2 answers

You can use your own tree, which allows you to duplicate elements instead of heaps. However, you can use TreeMap<PriorityKey, LinkedHashSet<Value>>. All operations: O (log priorityType):

  • add get(priority).add(value)if get returns nullput(priority, new LinkedHashSet())
  • deleting an arbitrary element is similar, except for the need to remove priority from the map if the set is empty.
  • poll () -

-

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;

However, if you need to change the priority you need to delete and add an item.

+2
source

, NavigableMap : " " " ", , .

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

TreeMap NavigableMap , , firstEntry/lastEntry .

+1

More articles:


All Articles