2

We all know that in Algorithms subject of Computer Science Min Heaps and Max Heaps are basically priority queues.

I have implemented various methods of heaps like build_heap,heapify,increase key,etc.

So now,that I have acquired a good understanding of it,I wanted to take advantage of the functional aspect of Java language.

I googled and found PriorityQueue.

As I proceeded to learn about them,I could not find any inbuilt methods like:

increase_key(x,k)

decrease_key(y,K)

I am using heaps for implementation of Dijkstra algorithm and it has use of the above two operations but now I think I have to go for my own heap implementation.

Did I miss something in my googling?

J J
  • 165
  • 6
  • 1
    Unfortunately the built-in `PriorityQueue` implementation doesn't support a `decreaseKey()` operation. See [this](http://stackoverflow.com/questions/6267172/which-datatype-to-use-as-queue-in-dijkstras-algorithm) as well. – Vlad Sep 10 '15 at 10:58

2 Answers2

2

What you could do ... each item that you insert in the PriorityQueue should have an attribute to store its value. Then you should create a custom comparator that uses this value to prioritize the queue's items. When you want to change an item's value you could remove the item from the PriorityQuery, modify its value and add it again to the value. The custom comparator will be triggered to prioritize it in the queue.

For more info on how to use the PriorityQuery (e.g. creating a custom comparator and relating it the the PriorityQueue see this post)

Community
  • 1
  • 1
Mike Argyriou
  • 1,250
  • 2
  • 18
  • 30
  • the post was helpful.But still thinking about using my own implementation.What I thought there were explicit functions defined already.Thanks anyways. – J J Sep 10 '15 at 11:21
1

While PriorityQueue is indeed a heap, it's not a "school heap" that would have internal functionality visible to you. PriorityQueue has the necessary functionality to do what it does best (i.e. sort items by a priority). It's not a starting point for making your own algorithms.

You wouldn't start creating a binary tree from a TreeSet either.

Kayaman
  • 72,141
  • 5
  • 83
  • 121