How to implement priority queue in C programming?

3
votes

I need to implement a priority queue in C programming using singly linked list.

I do not have a clear idea about priority queue. I googled but didn't fully understand what I found. My understanding is that a priority queue is a queue whose elements are ordered by priority. Insertions into the list are positioned within the list on the basis of the element priorities.

Lets say,we have following scenario. (Note : I assume, higher value goes with higher priority):

Element-->2 (priority=2)  (Now in position 0)

If another element needs to be inserted, say Element-->3 (priority=3) which has a higher priority.

I can move the previous element, Element-->2 (priority=2), and insert this new Element-->3 (priority=3) at position 0 with Element-->2 (priority=2) moved to position 1 in the list.

Now the list becomes,

Element-->3 (priority=3) followed by Element-->2 (priority=2)

Similarly, on the basis of insertion, do I have to shift all the elements in the list?

Is this correct?

5
cdata-structureslinked-listpriority-queue
So far so good -- have you gotten stuck with your implementation? - sarnold
simply speaking,when it has to operate on the list it takes the item with highest priority to operate upon...how you do this depends on whether you place highest priority element at the list front or you place it in the heap front(if you use heap)... - nikel

5 Answers

5
votes

You don't have to "shift" the list, instead when inserting you do something like this (pseudo-code):

if new_node.priority > list.head.priority:
    new_node.next = list.head
    list.head = new_node
else:
    previous = null
    for current = list.head:
        if current.priority < node.priority:
            previous.next = node
            node.next = current
            break loop
        previous = current

If your list has a pointer to the end, you can add a special check for a priority lower than the end as well.

4
votes

I think you are having trouble because a priority queue should be implemented with a heap tree, not a singly linked-list.

The heap makes everything easy -- all operations are very cheap: updating, deleting and inserting in the heap are all O(log n).

2
votes

You are OK with priority queues. But...

A linked list is not a simple array.

Each item in a linked list has a reference to the next item. You can insert an item after another one just by changing the references of these two items.

+--------+
| item A |                           +--------+
+--------+     +--------+            | item C |
|ref to B|---->| item B |            +--------+
+--------+     +--------+            |  NULL  |
               |  NULL  |            +--------+
               +--------+

Inserting C between A and B is performed by:

  1. changing NULL in C by ref to B
  2. changing ref to B in A by ref to C
0
votes

A priority queue is an Abstract Data Type which basically keeps items in it in sorted order (ascending or descending) on some chosen key. As mentioned by Anthony Blake, the heap implementation is the most straight forward, the underlying structure you use is simply an array and you perform some manipulation centered the array index.

If for some reason you want to implement using a singly linked list, below is a demo code to perform sorted insertion in an in-place fashion:

void sortedInsert(struct node **headRef,int data){
struct node *newnode=(struct node *)malloc(sizeof(struct node));
assert(newnode);
newnode->value=data;
newnode->next=NULL;

if(!(*headRef) || data<(*headRef)->value){
    newnode->next=*headRef;
    *headRef=newnode;
}else{
    struct node *prev=*headRef;

    while(prev->next && prev->next->value<data)
        prev=prev->next;

    struct node *temp=prev->next;
    prev->next=newnode;
    newnode->next=temp;
}

}

0
votes

Ok, i don't know why you need it in C. In C++ STL it is available.

But as you want here is the link to source code of your ask.

http://matrixsust.blogspot.com/2011/11/basic-priority-queue-in-c.html

OR

http://www.indiastudychannel.com/projects/4870-Priority-queue-using-array.aspx

Hope it helps.