Priority Queue - newell-romario/DSA GitHub Wiki

A priority queue data structure is concerned with storing the elements by their associated priority (i.e. elements with lower priorities are stored first or elements with higher priority are stored first).

A heap specifically a binary heap is a common way of implementing a priority queue. A binary heap comes in two types either it's a max heap or a min heap.

A binary heap is fundamentally a binary tree, the binary in it's name comes from a binary tree. In a binary heap the children in the sub tree are always <= or >= to the root of the sub tree depending on whether it's a min or max heap. A binary heap has a few properties:

1. The height is always lg n.
2. It has maximum number of nodes at all depth except at depth h.
3. The tree is filled from left to right.

We can implement a binary heap as either a tree or ingeniously impose a tree structure on an array. Imposing the tree structure on the array is the most common way of implementing a binary heap. We can use level order numbering to achieve this. Let's define p(r) to return the position of the root R. If we define the root of the tree to be p(r) = 1, then we can define it's children as 2p(r) and 2p(r) + 1 for left and right children respectively. With this in mind every node in the tree has a unique number and that unique number can be used to as an index into the array. See Introduction to Algorithms Section 6 for a better explanation.

Our priority queue implementation can be used by including the header file r2_heap.h.

A priority queue is represented by the structure below:

struct r2_pq{
        struct r2_locator **data;/*stores data along with position in heap*/
        r2_uint16 type;/*type of heap*/
        r2_uint64 ncount;/*current number of elements*/
        r2_uint64 pqsize;/*size of pq*/ 
        r2_cmp kcmp;/*A callback comparison function*/
        r2_fd  fd;/*A callback function frees memory used by data*/
        r2_cpy cpy;/*A callback function to copy key*/
        #ifdef PROFILE_HEAP
                r2_uint64 ncomp;/*number of comparison*/
        #endif
};

The fields data, type, ncount, and pqsize should not be modified or accessed.

Creating a priority queue is fairly simple. We can create a priority queue as seen below:

/*Type is either 0 for min heap or 1 for max heap*/
struct r2_pq *pq = r2_create_priority_queue(pqsize, type, cmp, fd, kcpy);

When creating a priority queue the arguments type and cmp is required. Example of the comparison function for a heap:

r2_int16 cmp(const void *a, const void *b)
{
        const r2_int64 *c = a; 
        const r2_int64 *d = b; 
        if(*c <= *d)
                return 0;
        return 1;
}

r2_destroy_priority_queue(pq);

struct r2_locator *loc = r2_pq_insert(pq, data);
if(loc != NULL)
  printf("\nSuccess");

We do not modify any of the fields in the locator directly.

/*Getting the root*/
struct r2_locator *root = r2_pq_first(pq);
/*Removing the root*/
if(r2_pq_remove(pq, loc))
   printf("\nSuccess");