Sorting with continous input

Question

I'm designing (not writing, yet) a task scheduler system for a complex video game. The rest of the program passes it objects containing a function and some metadata including an estimation of how much time is left before the data is needed (which can change, of course). The scheduler is responsible for prioritizing these tasks and calling the function.

The algorithm I've designed for this problem is pretty simple; it just sorts its list of task objects, pops one off the top, calls it, and repeats. Of course it's actually more complex than that (has to handle situations where things just can't get done on time, telling other parts of the code that their task just got bumped down the list...), but that's the gist of it.

I'd like some advice on the subject of how I'm going to sort that list. This loop will, obviously, be running constantly while the program is running. I'm thinking I'll use a slight modification of a bubble sort algorithm, running one pass on each iteration. The list won't be properly sorted for the first few cycles, but since the list will likely be very small when the program is started I expect it will be able to reliably get things into position as fast as they come in.

Has anyone done this before, and how did it work? Are there better ways I could do this?

Answer 1

You should be using a Priority Queue here. A Priority Queue is a queue in which items added to the queue have a priority, and whenever you get an item, you get the item with the minimum (or maximum, depending on implementation) priority.

Priority Queues are generally implemented using a min-heap (or max-heap). It will logically represent the data as a completely balanced tree in which each node is "less than" all of its children. It's not technically a binary search tree, in which the data is fully sorted. (Which is a viable alternative that is only slightly more expensive.) Since the data isn't actually completely sorted it means the only real meaningful operations you can perform are "Give me the lowest value" and "add this new value to the collection". (Incidentally, those are exactly the two operations that you need.) Both of which can be performed in O(log(n)) time. Because the min-heap ensures that the tree is always entirely balanced there is very little variance in the best/worst case. Even it's worst case is quite low, unlike a binary search tree which, if it gets unbalanced, can devolved into O(n) operatiosn.