6 Replies - 1496 Views - Last Post: 17 April 2012 - 10:49 AM Rate Topic: -----

#1 Ruru123  Icon User is offline

  • D.I.C Head

Reputation: 0
  • View blog
  • Posts: 59
  • Joined: 09-October 11

Priority Queues

Posted 17 April 2012 - 09:57 AM

Hi All,

I didn't know where to post this question - because it is not programming related..

How can a heap be used to represent a priority queue? (no code - just explanation pleasee)
I have researched for it in many places but I don't seem to be getting any beneficial answers. :/

Thank you
Is This A Good Question/Topic? 0
  • +

Replies To: Priority Queues

#2 sepp2k  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 2089
  • View blog
  • Posts: 3,181
  • Joined: 21-June 11

Re: Priority Queues

Posted 17 April 2012 - 10:02 AM

A (max) heap already fulfills all the requirements for a priority queue, doesn't it? So just use it.

... I guess I don't really understand the question.
Was This Post Helpful? 0
  • +
  • -

#3 Ruru123  Icon User is offline

  • D.I.C Head

Reputation: 0
  • View blog
  • Posts: 59
  • Joined: 09-October 11

Re: Priority Queues

Posted 17 April 2012 - 10:06 AM

View Postsepp2k, on 17 April 2012 - 10:02 AM, said:

A (max) heap already fulfills all the requirements for a priority queue, doesn't it? So just use it.

... I guess I don't really understand the question.


lol to be honest with you, i'm rather confused myself... from what I have read.. I've established that a priority queue is a data structure for maintaining a set of elements, each with an associated value and that a priority queue is based on a heap. I also found out that the most common way to implement a priority queue is to use a heap.

But my question is how is it based on a heap... How does a heap represent a priority queue?
Was This Post Helpful? 0
  • +
  • -

#4 sepp2k  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 2089
  • View blog
  • Posts: 3,181
  • Joined: 21-June 11

Re: Priority Queues

Posted 17 April 2012 - 10:16 AM

A heap represents a priority queue by allowing all the operations that are required of a priority queue.

For example a priority queue allows the user to add items to it. A heap supports that. It also allows the user to remove the item with the highest priority. A heap allows that as well.
Was This Post Helpful? 1
  • +
  • -

#5 Ruru123  Icon User is offline

  • D.I.C Head

Reputation: 0
  • View blog
  • Posts: 59
  • Joined: 09-October 11

Re: Priority Queues

Posted 17 April 2012 - 10:24 AM

View Postsepp2k, on 17 April 2012 - 10:16 AM, said:

A heap represents a priority queue by allowing all the operations that are required of a priority queue.

For example a priority queue allows the user to add items to it. A heap supports that. It also allows the user to remove the item with the highest priority. A heap allows that as well.


So, why does basing the data structure on a heap give computational advantages other than: a heap avoids the long paths that can arise with binary search tree??

Thank you
Was This Post Helpful? 0
  • +
  • -

#6 sepp2k  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 2089
  • View blog
  • Posts: 3,181
  • Joined: 21-June 11

Re: Priority Queues

Posted 17 April 2012 - 10:30 AM

I'm not sure I understand the question. Using a heap, rather than a binary search tree, as a priority queue makes sense because getting the element with the highest priority from a heap is an O(1) operation, whereas it would be O(log n) for a balanced BST (which I guess is what you meant about the long paths?). You don't really need more reasons than that.

That being said a priority queue that is implemented as a BST would still be a priority queue.
Was This Post Helpful? 1
  • +
  • -

#7 Ruru123  Icon User is offline

  • D.I.C Head

Reputation: 0
  • View blog
  • Posts: 59
  • Joined: 09-October 11

Re: Priority Queues

Posted 17 April 2012 - 10:49 AM

Thank you soo much :)
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1