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?

Reese Moore
  • 11,524
  • 3
  • 24
  • 32
user472221
  • 3,014
  • 11
  • 35
  • 42

2 Answers2

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.

Naveen
  • 4,456
  • 2
  • 22
  • 16
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