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?

Answer 1

As mentioned by Anthony Blake, a priority queue is meant to be implemented with a heap tree, which can be represented as an array. In such an array, tree nodes are placed level-by-level. The index of the parent of node at index i can then be calculated as (i - 1) / 2 and the two children are at 2 * i + 1 and 2 * i + 2. E.g., the tree

   2
 4   6
5 8 9 7

would be saved as [2, 4, 6, 5, 8, 9, 7].

For the implementation, we first define a struct and a swap function:

typedef struct pair pair;
struct pair {
    size_t node;
    size_t distance;
};

void swap(pair queue[NODES], size_t i, size_t j) {
    pair temp = queue[i];
    queue[i] = queue[j];
    queue[j] = temp;
}

Let us assume we are implementing a min priority queue for the Dijkstra algorithm, where the graph has NODES vertices. The node with the smallest key will always be in the root. When we dequeue it, we replace it with the last node and bubble down the node until it is in the right place - key is smaller than the keys of both children.

size_t dequeue(pair queue[NODES], size_t size) {
    size_t root = queue[0].node;
    queue[0] = queue[--size];

    // Loop while at least one child exists
    for (size_t curr = 0; 2 * curr + 1 < size;) {
        size_t min_cost = 1;
        if (2 * curr + 2 < size &&
            queue[2 * curr + 2].distance < queue[2 * curr + 1].distance) {
            min_cost = 2;
        }

        if (queue[curr].distance <= queue[2 * curr + min_cost].distance) {
            break;
        }

        swap(queue, curr, 2 * curr + min_cost);
        curr = 2 * curr + min_cost;
    }

    return root;
}

To enqueue a new node, we place at at the first empty spot and bubble it up until it is in the right place - parent key is smaller.

void enqueue(pair queue[NODES], size_t node, size_t distance, size_t size) {
    queue[size] = (pair){node, distance};
    bubble_up(queue, size);
}

Similarly, we decrease the key of a node. We find it in the tree, decrease its key and bubble it up.

void decrease_key(pair queue[NODES], size_t node, size_t distance, size_t size) {
    size_t curr = 0;
    for (; curr < size && queue[curr].node != node; ++curr);
    queue[curr].distance = distance;
    bubble_up(queue, curr);
}

We can prevent looping over the whole array by having another array which tells us the position of each node in the heap.

The function bubble_up can be written as

void bubble_up(pair queue[NODES], size_t curr) {
    while (curr > 0) {
        size_t parent = (curr - 1) / 2;
        if (queue[parent].distance <= queue[curr].distance) {
            break;
        }
        swap(queue, parent, curr);
        curr = parent;
    }
}

If all the nodes and keys are available beforehand, we can decrease the time complexity of creating the initial heap from O(nlogn) to O(n) by bubbling it from bottom to the top - heapify.

Answer 2

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 = 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;
  }
}

Answer 3

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.

Answer 4

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.

Answer 5

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

Answer 6

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