How to efficiently reuse released ids in id sequence

user_1079475 0
Viewed 86

Lets say we have PID generator that generated 7 ids for 7 processes {1,2,3,4,5,6,7}. Process 3 and 6 have finished and id 3 and 6 are up for grabs. Now we start three new processes. How to implement efficient algorithm that will first assign them ids 3, 6, and 8 in this very sequence.

I was thinking about storing released Ids in a sorted tree, but that takes extra structure to track the 'holes' in the sequence. Having sorted tree structure of ids in use helps to get next biggest id, but does it give any upper hand in finding the holes?

space-complexity generator data-structures time-complexity algorithm
1 Answers

Just use a priority queue(heap) to trace all the hole, like this:

#include <queue>

std::priority_queue<int> q;
int all_free_after = 1;

void free_one_pid(int pid) {
    // the priority_queue returns the largest one inside the queue
    // but we want the smallest one
    // so we are push the opposite number into the queue
    q.push(-pid);
}

int get_one_pid() {
    if (q.empty()) { return all_free_after++; }
    int res = -q.top();
    q.pop();
    return res;
}
user_145763800
Related