Implement Priority Queue Using Binary Heaps

Priority Queue:
A priority queue is an abstract data type where the elements in the queue has a "priority" associated with it.  The order in which the elements are stored/added/removed is decided by the priority associated with the element.

• The element with high priority will be processed before the low priority element.
• If two elements have same priority, then the element added earlier in the queue would get processed.

And the Priority Queue can be implemented using Binary Heaps.

Heap Properties:
Structure Property:  For any element in i th position of the array, the left and right child present are at the position (2i + 1) and  (2i + 2) correspondingly.

Heap Order Property:
The key value of parent needs to be smaller or equal to the key value of its children.


Input from user:  90  25  30  15  7  19

How to construct a Binary Heap?
Below are the steps to construct Binary Heap.

           +----------------------------------------+
input :  |  90  |  25  |  30  |  15  |  7  |  19  |
           +----------------------------------------+
index:      0        1       2       3       4      5

Step 1: Construct binary tree from the given array.
Root node is located at the index 0 of the array.  The location of its left and right children are calculated as below.

i = 0, input[0] is 90
Here, i is the index and 90(input[i]) is the root node.
2*i + 1 = 2*0 + 1 = 1
2*i + 2 = 2*0 + 2 = 2
Left child is located at index 1, which is 25.
Right child is located at index 2, which is 30

                             90
                         /        \
                      25          30


i = 1, input[1]  is 25
2*i + 1 = 2*1 + 1 = 3
2*i + 2 = 2*1 + 2 = 4
Left child is located at index 3, which is 15.
Right child is located at index 4, which is 7

                             90
                         /        \
                      25          30
                   /      \     
                 15      7 


i = 2, input[2] is 30
2*i + 1 = 2*2 + 1 = 5
Left child is located at index 5, which is 19.
no right child

                             90
                         /        \
                      25          30
                   /      \      /
                 15      7    19

Step 2: Check whether heap order property is violated in the above constructed tree.
Heap Order Property:  The key value of parent needs to be smaller or equal to the key value of its children.

To verify heap order property on binary heap, we need to start from the nodes(7 and 19 - level 1) that are present immediately above the leaf.
                             90
                         /        \
                      25          30
                   /      \      /
                 15       7  19

19 is not greater than 30.  So, heap order property is not violated at the node with value 30.

If the node which we are currently processing has two children, then compare the smallest child with the parent.  If the key value of child is smaller than parent, then swap their key values.

15 and 7 are children of 25.
7 is the smallest child
Parent Key value(25) is greater than child's key value(7).  So, swap the key values.

                             90
                         /        \
                       7          19
                   /      \       /
                 15      25   30

Similarly, apply heap order property across the binary tree.
                             7
                         /        \
                      90          19
                    /      \       /
                 15      25   30


Resultant Binary Heap:
                             7
                         /        \
                      15          19
                    /      \       /
                 90      25   30


How to inserting a new node into the Binary Heap?

                             7
                         /        \
                      15          19
                    /      \       /
                 90      25   30

Insert a new element 12 to the above binary heap.

                             7
                         /        \
                      15          19
                    /      \       /   \
                 90      25   30    12

Heap order property violated at level 1.
30 and 12 are children of 19.
12 is the smallest child
Parent Key value(19) is greater than its child key value(12).  So, swap the key values.

Resultant Binary Heap:
                             7
                         /        \
                      15          12
                    /      \       /   \
                 90      25   30    19

How to Delete a node from Binary Heap?
                             7
                         /        \
                      15          12
                    /      \       /   \
                 90      25   30    19

Swap the value of root node and the last leaf node
                            19
                         /        \
                      15          12
                    /      \       /   \
                 90      25   30    7

Delete the current last leaf node.
                            19
                         /        \
                      15          12
                    /      \       / 
                 90      25   30   

Apply heap order property to root node.
                            12
                         /        \
                      15          19
                    /      \       / 
                 90      25   30   

                            12
                         /        \
                      15          30
                    /      \       / 
                 90      25   19


How to replace a node in Binary Heap?
   
                            12
                         /        \
                      15          30
                    /      \       / 
                 90      25   19

Replace 12 with 17.

                            17
                         /        \
                      15          30
                    /      \       / 
                 90      25   19

Heap order Property is violated at root node.

Resultant Binary Heap:
                            15
                         /        \
                      17          30
                    /      \       / 
                 90      25   19


See Also:
C Program To Represent Binary Search Tree Using Arrays
C Program To Perform Insertion, Deletion and Traversal In Binary Search Tree
C Program To Implement Binary Tree Traversals: In-order, Pre-order and Post-order
C Program To Implement Dictionary Using Binary Search Tree
C Program To Perform Searching in Binary Search Tree

C Program To Perform Insertion, Deletion & Traversal In Threaded BST

C Program To Perform Insertion, Deletion And Traversal In Red Black Tree
C Program To Perform Insertion, Deletion and Traversal in AVL Tree
C Program To Perform Insertion, Deletion and Traversal In B-Tree
C Program To Implement Priority Queue Using Binary Heaps
Construct Binary Search Tree From In-order and Pre-order Traversal Outputs

Example Program To Implement Priority Queue Using Binary Heaps(in C):

---

  #include <stdio.h>
  #include <stdlib.h>

  #define HEAPCOUNT 100

  int count = 0;

  /*
   * find the smallest among the left(data[pos])  and
   * right child(data[pos + 1]).  Check whether the smallest
   * among them is lesser than their parent.  If so, swap
   * parent and the node with smallest value.  Continue the
   * above processing from index "low" to "count"
   *         40
   *        /   \
   *       10   30
   *  10 is smaller tha 30. 10 is comapared with its parent
   *  and it is smaller(10 < 40).  So, swap parent and 10.
   *         10
   *       /    \
   *      40    30
   */

  void insertHeap(int *data, int low, int count) {

        int pos = (2 * low) + 1, current = data[low];

        while (pos <= count) {

                if (pos < count && data[pos] > data[pos + 1])

                        pos++;

                if (current <= data[pos])

                        break;

                else {

                        data[low] = data[pos];

                        low = pos;

                        pos = (2 * low) + 1;

                }

        }

        data[low] = current;

        return;

  }

  /*

   * To construct a heap we always consider the 

   * nodes which are present above the leaf.  Here,

   * nodes present after data[n/2 - 1] are leaf nodes

   * insertHeap() - used for restoring the heap

   * data - holds node values & n - node count

   */

  void buildHeap(int *data, int n) {

        int low;

        for (low = n/2 - 1; low >= 0; low--) {

                insertHeap(data, low, n-1);

        }

        return;

  }

  void buildUp(int *data, int index) {

        int val = data[index];

        /* if parent of the current node has value

         * greater than its child, then swap parent

         * and child nodes.  Traverse up the tree

         * until u hit a condition where parent node

         * is having lesser value than children

         */

        while (data[(index - 1) / 2] >= val) {

                data[index] = data[(index - 1) / 2];

                if (!index)

                        break;

                index = (index - 1) / 2;

        }

        data[index] = val;

        return;

  }

  /* adding new node to the binary heap */

  void addNode(int *data, int val, int n) {

        data[n] = val;

        buildUp(data, n);

        return;

  }

  /* delete a node from binary heap */

  void deleteNode(int *data, int n) {

        int val = data[0];

        data[0] = data[n];

        insertHeap(data, 0, n - 1);

        printf("%d is deleted from the heap\n", val);

        return;

  }

  /* replacing root node with value val */

  void replaceNode(int *data, int val, int n) {

        int i;

        data[0] =  val;

        for (i = n/2 - 1; i >= 0; i--)

                insertHeap(data, i, n - 1);

        return;

  }

  void display(int *data, int n) {

        int i;

        printf("\nData in Binary Heap:\n");

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

                printf("%d ", data[i]);

        }

        printf("\n\n");

  }

  int main() {

        int n, i, *data, temp, ch, val;

        data = (int *)malloc(sizeof(int) * HEAPCOUNT);

        printf("Enter the no of elements(1-80):");

        scanf("%d", &n);

        if (n < 1 || n > 80) {

                printf("Threshold Exceeded!!\n");

                return 0;

        }

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

                printf("Input %d:", i + 1);

                scanf("%d", &data[i]);

                count++;

        }

        buildHeap(data, n);

        while (n  < (HEAPCOUNT -1)) {

                printf("1. Add New Node\t2. Delete Node\n");

                printf("3. Replace Node\t4. Display Heap\n");

                printf("5. Exit\nEnter your choice:");

                scanf("%d", &ch);

                switch(ch) {

                        case 1:

                                printf("Enter your input:");

                                scanf("%d", &val);

                                addNode(data, val, n);

                                n++;

                                break;

                        case 2:

                                deleteNode(data, n -1);

                                n--;

                                break;

                        case 3:

                                printf("Enter input value:");

                                scanf("%d", &val);

                                replaceNode(data, val, n);

                                break;

                        case 4:

                                display(data, n - 1);

                                break;

                        case 5:

                                goto sort;

                        default:

                                printf("Wrong Option!!\n");

                                break;

                }

        }

  sort:

        /* swap root and current last node, then perform

         * restore heap to get data in sorted order.  Basically,

         * we are performing insort operation.

         */

        for (i = n - 1; i > 0; i--) {

                temp = data[i];

                data[i] = data[0];

                data[0] = temp;

                insertHeap(data, 0, i - 1);

        }

        printf("Sorted Data:\n");

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

                printf("%d ", data[i]);

        printf("\n");

        return 0;

  }

  Output:(C Program To Implement Priority Queue Using Binary Heaps)

  jp@jp-VirtualBox:~/$ ./a.out
  Enter the no of elements(1-80):6
  Input 1:90
  Input 2:25
  Input 3:30
  Input 4:15
  Input 5:7
  Input 6:19
  1. Add New Node 2. Delete Node
  3. Replace Node 4. Display Heap
  5. Exit
  Enter your choice:1
  Enter your input:12

  1. Add New Node 2. Delete Node
  3. Replace Node 4. Display Heap
  5. Exit
  Enter your choice:3
  Enter input value:17

  1. Add New Node 2. Delete Node
  3. Replace Node 4. Display Heap
  5. Exit
  Enter your choice:4

  Data in Binary Heap:
  12 15 17 90 25 30 19 

  1. Add New Node 2. Delete Node
  3. Replace Node 4. Display Heap
  5. Exit
  Enter your choice:5

  Sorted Data:
  90 30 25 19 17 15 12