What is the best way to implement a queue with two priorities?

Question

I would like to implement a bidirectional priority queue with the following restrictions:

• must be implemented in an array of fixed size. 100 elements. If you need to add new elements after filling the array, you need to delete the oldest file

• need maximum and minimum in O (1)

• if possible, insert into O (1)

• if possible remove the minimum at O ​​(1)

• clear empty / init state in O (1) if possible

• the number of elements in the array at the moment in O (1)

I would like O (1) for all of the above 5 operations, but it was impossible to have O (1) for all of them in the same implementation. Atleast O (1) for 3 operations and O (log (n)) for the other 2 operations should be enough.

Understand if any pointers can be provided for such an implementation.

Answer 1

There are many specialized data structures for this. One simple data structure is the min-max heap, which is implemented as a binary heap, where the layers alternate between the “minimum layers” (each node is less than or equal to its descendants) and the “maximum levels” (each node is greater than or equal to its descendants.) Minimal and maximum values ​​can be found in O (1) time, and, as in the standard binary heap, queues and time intervals can be performed in O (log n) time each time.

You can also use the interval heap data structure , which is another specialized priority queue for the task.

Alternatively, you can use two priority queues: one storage item in ascending order and one in descending order. Whenever you insert a value, you can insert elements in both priority queues and each of them stores a pointer to the other. Then, whenever you deactivate min or max, you can remove the corresponding element from another heap.

As another option, you can use a balanced binary search tree to store items. Minimum and maximum values ​​can be found in O (log n) time (or O (1) if you cache the results), and insertions and deletions can be performed in O (log n) time. If you use C ++, you can simply use std::map for this, and then use begin() and rbegin() to get the minimum and maximum values, respectively.

Hope this helps!

Answer 2

A binary heap will let you insert and remove a minimum in O(log n) , and the rest in O(1) .

The only tricky part is deleting the oldest element after filling the array. To do this, save another array:

 time[i] = at what position in the heap array is the element added at time i + 100 * k. 

Every 100 iterations you increase k .

Then, when the array is filled for the first time, you delete heap[ time[0] ] , when it is filled the second time, when you delete heap[ time[1] ] , ... when it is filled for the 100th time , you wrap around and delete heap[ time[0] ] again, etc. When it is filled for k th times, you will remove heap[ time[k % 100] ] (100 is your array size).

Be sure to update the time array when you insert and delete elements.

Removing an arbitrary element can be done in O(log n) if you know its position: just replace it with the last element in the heap array and sift the element that you changed.

Answer 3

If you absolutely need max and min to be O (1), then you can create a linked list where you constantly keep track of min, max and size, and then link all the nodes to some kind of tree structure, probably a bunch. Min, max and size will be constant, and since the search for any node will be in O (log n), insert and delete will be recorded each. Cleaning will be trivial.

Answer 4

If your queue has a fixed size, then O-notation does not make sense. Any O (log n) operation or even O (n) operation is essentially O (1), since n is fixed, so you really want to use an algorithm that is fast for a given dataset. Probably two parallel priority queues for the heap would be accurate (one for high, one for low).

If you know more about what data you have, you can do something more targeted.