You may want to read the post “heap” first.

**Priority Queue**

A priority queue is a data structure that supports at least the following two operations,

1. insert: insert an item with priority

2. pull_min_element/pull_max_element: depends on your priority queue type (min priority-queue or max-priority-queue), the operation find the item with min/max priority, return the item and remove it from the queue.

A priority queue is usually implemented using a heap, but it doesn’t have to be.

A priority queue can be implemented using a simple linked list/array. Every time an insert operation occurs, we simply append it to the end of the list/array and when a pull request is issued, we iterate through the list/array and find the element to return and remove. Alternatively, we can keep the linked list/array sorted and simply remove the first item every time.

A priority queue can also be implemented using a self-balancing binary search tree (e.g. red-black tree). In this case, both insert and pull take O(logn) worst case running time.

But the most commonly used data structure for priority queue is heap. The simplest heap is binary heap. For the convenient of discussion, the description below assumes min binary heap.

When binary heap is used to implement a priority queue, both insert and pull can be done in O(logN) worst case time. Insert has an average of constant time. To build the heap from already exist N items, it takes O(N) worst case time.

**C Implementation using Heap**

The implementation of priority queue is just a simple wrapper of the heap implementation in the post “heap”.

`#include <stdio.h>`

`#include <stdlib.h>`

typedef struct heapData {

` //dummy`

} heapData;

typedef struct heapNode {

` int value;`

` heapData data; //dummy`

} heapNode;

typedef struct PQ {

heapNode* heap;

` int size;`

} PQ;

void insert(heapNode aNode, heapNode* heap, int size) {

` int idx;`

heapNode tmp;

idx = size + 1;

heap[idx] = aNode;

` while (heap[idx].value < heap[idx/2].value && idx > 1) {`

tmp = heap[idx];

heap[idx] = heap[idx/2];

heap[idx/2] = tmp;

idx /= 2;

}

}

void shiftdown(heapNode* heap, int size, int idx) {

int cidx; //index for child

heapNode tmp;

` for (;;) {`

cidx = idx*2;

` if (cidx > size) {`

break; //it has no child

}

` if (cidx < size) {`

` if (heap[cidx].value > heap[cidx+1].value) {`

++cidx;

}

}

` //swap if necessary`

` if (heap[cidx].value < heap[idx].value) {`

tmp = heap[cidx];

heap[cidx] = heap[idx];

heap[idx] = tmp;

idx = cidx;

` } else {`

` break;`

}

}

}

`heapNode removeMin(heapNode* heap, int size) {`

` int cidx;`

heapNode rv = heap[1];

` //printf("%d:%d:%dn", size, heap[1].value, heap[size].value);`

heap[1] = heap[size];

--size;

shiftdown(heap, size, 1);

` return rv;`

}

`void enqueue(heapNode node, PQ *q) {`

insert(node, q->heap, q->size);

++q->size;

}

heapNode dequeue(PQ *q) {

heapNode rv = removeMin(q->heap, q->size);

--q->size;

` return rv; `

}

void initQueue(PQ *q, int n) {

q->size = 0;

` q->heap = (heapNode*)malloc(sizeof(heapNode)*(n+1));`

}

int main(int argc, char **argv) {

` int n; `

` int i;`

PQ q;

heapNode hn;

n = atoi(argv[1]);

initQueue(&q, n);

srand(time(NULL));

` for (i = 0; i < n; ++i) {`

hn.value = rand()%10000;

` printf("enqueue node with value: %dn", hn.value);`

enqueue(hn, &q);

}

` printf("ndequeue all values:n");`

` for (i = 0; i < n; ++i) {`

hn = dequeue(&q);

` printf("dequeued node with value: %d, queue size after removal: %dn", hn.value, q.size);`

}

}

Compile the code using,

gcc -o pq pq.c

A sample run would be as below,

**References:**1. Wikipedia: http://en.wikipedia.org/wiki/Binary_heap

2. Programming Perls. 2nd Edition