priority queue data structure

Question

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?

Answer 1

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.