Thread: Applications of priority queues

  1. #1
    Registered User
    Join Date
    Jun 2010
    Posts
    22

    Unhappy Applications of priority queues

    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

  2. #2
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    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

  3. #3
    Registered User
    Join Date
    Oct 2008
    Posts
    1,262
    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.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Compiling C in Visual Studio 2005
    By emanresu in forum C Programming
    Replies: 3
    Last Post: 11-16-2009, 04:25 AM
  2. priority inversion due to pthread_mutex_lock(): how to avoid?
    By mynickmynick in forum C Programming
    Replies: 11
    Last Post: 04-07-2009, 10:34 AM
  3. crazy pipe/fork
    By fortune2k in forum C Programming
    Replies: 8
    Last Post: 03-13-2009, 11:28 AM
  4. Priority queue's
    By Cmuppet in forum C Programming
    Replies: 7
    Last Post: 11-23-2004, 02:21 PM
  5. BST implementation of priority queues
    By jcleong in forum C Programming
    Replies: 1
    Last Post: 05-14-2002, 09:09 AM