priority queue data structure
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 1
s.
When I call remove
it will first remove the 0
, but if I call remove
again will it remove all three 1
s 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?
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.
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
精彩评论