Hi all,
Please help me understanding the applications of priority queues as I am new to the subject od data structures....
Thanks in advance
Regards
C_Enthusiast
Hi all,
Please help me understanding the applications of priority queues as I am new to the subject od data structures....
Thanks in advance
Regards
C_Enthusiast
The CFQ scheduler in the linux kernel uses something like a priority queue (in fact: a RB tree, which I think could count as such a thing) to rank tasks on each processor. There are some complicating factors, but basically the idea is that when a process is switched out by the scheduler, it is added into the tree with a low priority (to the right), while the process furtherest left is run, and the other processes have their priorities re-evaluated (priority is measured as a time value). The reason this is not a simple linear queue is that the recalculation of the time value is not the same for everyone (hence, some processes with a higher prio "pass" others in the movement thru the tree with every clock tick).
Anyway, in short I'd say time ordered operations would be one common application for a priority queue.
C programming resources:
GNU C Function and Macro Index -- glibc reference manual
The C Book -- nice online learner guide
Current ISO draft standard
CCAN -- new CPAN like open source library repository
3 (different) GNU debugger tutorials: #1 -- #2 -- #3
cpwiki -- our wiki on sourceforge
Another example usage is the dijkstra algorithm. Each step you need to select some state with the shortest distance traveled so far. Setting the distance as the key in a priority queue means you can do this fairly easily: insert each state in the priority queue, and simply pop the next item to get the next state to deal with.