开发者

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 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?


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

0

上一篇:

下一篇:

精彩评论

暂无评论...
验证码 换一张
取 消

最新问答

问答排行榜