Priority Queue

[Parul Bagadia]

In case of applying deleting operation on ascending priority queue; elements are retrieved in ascending order.. however if a small element is inserted after several deletions; the next retrival will return that smsller element, which may be smaller than a previously retrieved element...
Above is the statement given in the book of Data Structures by Tenenbaum; but logically always the smallest item should be deleted, isn't it so?

[Ganon11]

In a priority queue, a deleteMin operation deletes the smallest element currently in the queue. It has no effect on elements that might enter the queue at a later time - how could it possibly do that?

In your example, you may have had a queue with the values 1, 2, 4, 5, and 6 in it. So you deleteMin 3 times and get (in order) 1, 2, and 4. Now I add 3 to the queue. It is now the smallest element in the queue (i.e. it is smaller than 5 and 6), so the next deleteMin will give 3.

[Parul Bagadia]

In a priority queue, a deleteMin operation deletes the smallest element currently in the queue. It has no effect on elements that might enter the queue at a later time - how could it possibly do that?

In your example, you may have had a queue with the values 1, 2, 4, 5, and 6 in it. So you deleteMin 3 times and get (in order) 1, 2, and 4. Now I add 3 to the queue. It is now the smallest element in the queue (i.e. it is smaller than 5 and 6), so the next deleteMin will give 3.

No, here my point is the following statement..
however if a small element is inserted after several deletions; the next retrival will return that smaller element, which may be smaller than a previously retrieved element...
which means that after several deletions if i add up some elements; still the smaller of the previously retrieved element will be retrieved.

[sicarie]

No, here my point is the following statement..
however if a small element is inserted after several deletions; the next retrival will return that smaller element, which may be smaller than a previously retrieved element...
which means that after several deletions if i add up some elements; still the smaller of the previously retrieved element will be retrieved.

Parul-

Please slow down and write this out, work it out on paper, on the computer, however works best for you - Ganon has answered you appropriately.

1) a priority queue - 1, 2, 4, 5, 6

2) after several deletions - so we remove 1, 2, and 4 - this queue is now 5, 6

3) if a mall element is inserted - say 3, so the queue is now 3, 5, 6

4) the next retrieval will return that element - the smallest element in the queue is 3, so that is the one returned

Does that answer your question, or is there a specific part/wording you have having trouble with?

[Parul Bagadia]

Parul-

Please slow down and write this out, work it out on paper, on the computer, however works best for you - Ganon has answered you appropriately.

1) a priority queue - 1, 2, 4, 5, 6

2) after several deletions - so we remove 1, 2, and 4 - this queue is now 5, 6

3) if a mall element is inserted - say 3, so the queue is now 3, 5, 6

4) the next retrieval will return that element - the smallest element in the queue is 3, so that is the one returned

Does that answer your question, or is there a specific part/wording you have having trouble with?

Oh yaeh, i got it.
Thank you very much.
Actually i made a mistake in understanding.
Thanx again.