• Post Reply Bookmark Topic Watch Topic
  • New Topic

Priority Queue using BST  RSS feed

 
Harish Shivaraj
Ranch Hand
Posts: 54
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hi all,

I’m in the process of implementing Priority queue, as I understand that there are many data structures you could use to implement. I implemented it with the an array, which it works absolutely fine. However I have limitations on what collections I can use from the collections classes. I fact I cant use any of the collections classes. Meaning I cant use array.

I’m trying to implement Priority Queue using heap. And implementing heap using binary trees. But however I have a few questions which I need to clarify and I cant think of any other way of resolving it. Ofcourse I can implement my own simple array class using linked list.

Inserting into heap would be quite simple, as I just need to find the right last position from left to right leaf to insert the node into the tree. However after inserting, you may want to make sure that leaf node values are > than root node. Therefore, the root node will always be with the highest priority.

I call these steps where you compare from top down as bubbledown and bubbleup. To do this I really need a for each node within the treee node to have attribute pointing to its root node. So in case of bubbleup I always have a pointer for a given node to its root, without it would mean I would to traverse through the entire tree to identify its root. Which I believe is very inefficient.

Or have I taken this completely wrong? Or is it the case that heap are only best with arrays and therefore use array (by implement it using linked list?)

Thanks
 
Paul Clapham
Sheriff
Posts: 22823
43
Eclipse IDE Firefox Browser MySQL Database
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
You shouldn't concern yourself with what might be "inefficient" or "best". What you are doing here is (a) learning to program Java, and (b) learning about priority queues and other data structures. In real life the "best" or "most efficient" implementation of a data structure is almost certain to be some code which somebody else already wrote, and in particular some class which is already in the standard Java API.
 
Harish Shivaraj
Ranch Hand
Posts: 54
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I agree, In real world I may never have to implement these data structures. However - I possibly couldn't argue on that point with my professor. The least he would fail me :P. What im after is to find out what the best way to implement a heap. Almost everywhere I see, its most commonly implemented using an ordered list - which is quiet commonly an array using collection ArrayList. As long as using ArrayList your fine. As there is no limit to size of the queue, you can keep appending to the ArrayList. But when you have barriers on not using ArrayList, the challenge of implementing your own hits you quite hard.

Thus my question on whether is it best to implement using simple Array Class of my own using linked list or use binary tree. And I was thinking of binary tree as it takes must of the overhead involved with the Arrays. Where as with the Tree it makes things much simpler and don’t worry about multiple data structures to maintain.

As long as I find out how to implement heap using binary tree, I think binary tree would be the best way going forward. However I want more of your opinion on this and argue it isnt.
 
Winston Gutkowski
Bartender
Posts: 10575
66
Eclipse IDE Hibernate Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Paul Clapham wrote:What you are doing here is (a) learning to program Java...

Actually, I'd say that Harish is learning to program, period.

@Harish: And that's not meant to be a put-down; simply that you're learning one of the fundamental parts of programming: algortihms.

The only thing I'd take issue with is your "implementing heap using binary trees" statement. A heap is a binary tree (indeed, a balanced binary tree, because the structure mandates it); but NOT all binary trees are heaps (Java's "Tree" implementations being just one case in point).

I think also that you may be confusing a "priority queue" with a queue. The former comes in all shapes and sizes, whereas a queue is simply a line - ie, a structure that allows only as many items to be extracted as are currently in it, and may allow only a certain number of items to be inserted (although I'm pretty sure it isn't a requirement).

A "priority queue" is simply one that mandates the extraction process - presumably something other than "first in first out"; otherwise, it's just a queue.

And a "last in first out" queue is a stack - the first (I think) computer structure ever discovered.

Connect two stacks in series, and you have a pipe (a "buffered" form of queue). For any other type of "priority" (eg, an "alphabetic" queue) you need some sort of data structure between the input and output that satisfies the output requirement; but a queue is a queue is a queue...

Not sure whether it helps or not; but hopefully.

Winston
 
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!