Hi,

I am trying to understand priority queue. I have downloaded a lecture slide form the link:
http://www.bowdoin.edu/~ltoma/teaching/cs210/spring09/Slides/210-PQueue.pdf
(sorry its not inserting using Link)

However, on slide 5 it provides an example which I have attached. I can understand insert(3, B) which is at the end of queue. But I cant understand insert (7,D) which is in the middle. Can some body please guide me is this stuff correct or not? Is there any other good example of priority queues using arrays?


Zulfi.

 

Is that a minheap or a maxheap?

What is the mapping between the tree and the array?

Are you sure this isn't just a hypothetical example showing the interface behavior of the priority queue?

 

Hi,
I am teaching a queue lecture which includes description about priority queues. But its not related to Heap. Moreover, I am using array based Queue. There is no involvement of trees.

Is that a minheap or a maxheap?

What is the mapping between the tree and the array?

I am looking for an example of priority queue with no connection with heap. I cant understand what type of ordering is used in the example related to above web link. Please guide me what type of ordering is used? Moreover they are using a "set" .

Zulfi.

 

I don't think that there IS any internal ordering in that example data structure -- and there doesn't have to be.

Do you understand what a priority queue is?

ALL that is required is that when you retrieve a value from the priority queue it is the extreme value (generally the smallest). So you can store your data in random order and then simply search the entire data set every time you want to get a value from it. Not very efficient, but perfectly valid.

They can't use a set data structure because a set is not allowed to have duplicates and there is no constraint that says that you can't have multiple entries in a priority queue that have the same priority or are even identical. Why do you think they are using a set? Is it because they used curly braces in their example? I wouldn't read too much into that.