Priority queue with change priority function that preserves ordered items
I am looking for a way to schedule threads by priority and First-Come-First Serve (FCFS) when two threads have the same priority. I was thinking about using a bunch of queues or something. The problem is that even if I implement my own priority queue, being able to change priorities destroys the order of insertion into that queue.
To solve this problem, I can save the insert time of each thread and sort the priority queue also by the insert time (as a secondary parameter to the first Priority parameter), but I believe there is a combination of data structures that can solve the problem without using insert time.
The complexity should be O(logN)
(there are some naive solutions with complexity O(N)
, such as having a regular queue and iterating over the queue whenever we have to pop up a stream).
source to share
Maybe I misunderstood your problem, but you can have a separate list for each priority.
Therefore, each thread is added to the corresponding list based on its priority. And since you always add at the end of the list and remove from the head, you will have FCFS behavior.
You can also create a priority queue to get the next lowest priority thread (O (1) to get the next thread and O (logN) to insert. For comparison, you can use a combination of priority and insert time of each node.
source to share