Priority Queue Data Structure

Question

Suppose I have a priority queue that deletes items in ascending order, and the items are stored in this queue 1, 1, 3, 0, 1. Incremental order 0, then 1, then 3, but there are three elements of 1s.

When I call remove, it will delete first 0, but if I call remove, it will delete all three again 1, or I will need to call removethree separate ones to delete all elements 1.

Does a call removein such a priority queue call all elements with the same minimum value, or is only one element deleted during each call?

Answer 1

In a priority queue, usually a delete operation deletes a single record containing the maximum value. So in your case this will be the second option. The withdrawal order is not guaranteed. Any key with a "maximum" value will be deleted. In addition, an unsorted array represents a poor data structure for implementing a priority queue. You typically use a heap data structure to get O (log (n)) guarantees when inserting and deleting.

Answer 2

a typical heap implementation will always restore the tree, so it will delete 0, 1, 1, 1, and then 3, since 1 will get a push to the root during regapification.

Am I mistaken?

edit: your case is a mini-heap