How to implement priority queue in C programming?

Question

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?

Solution 1

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.

Solution 2

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).

Solution 3

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