3

Suppose that I have a priority queue which removes elements in increasing order, and stored in this queue are the elements 1, 1, 3, 0, 1. The increasing order is 0 then 1 then 3, but there are three element 1s.

When I call remove it will first remove the 0, but if I call remove again will it remove all three 1s at the same time, or will I need to call remove three separate times to remove all of the 1 elements.

Does a call to remove on such a priority queue remove all elements of the same minimum value or will only one element be removed with each call?

Improve this question
2
  • 1
    Not a real question unless you say what implementation you're using. Commented Nov 20, 2010 at 3:59
  • "An unsorted array"? In that case, you're implementing the data type yourself and so you can decide what you want to do... Commented Nov 20, 2010 at 12:05

2 Answers 2

Reset to default
3

In a priority queue usually the remove operation removes a single record containing the maximum value. So in your case it would be the second option. The order of removal is not guaranteed. Any key with the "maximum" value would be removed. Also, unsorted array is a bad data structure of implement a priority queue. You would typically use a heap data structure to get O(log(n)) guarantees on insertion and removal.

Improve this answer
Sign up to request clarification or add additional context in comments.

Comments

0

typical heap implementation would always reheap the tree therefore it would remove 0, 1, 1, 1 and then 3 as 1 would get push to the root during reheapification..

am i wrong?

edit: your case is a min-heap

Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.