Min Priority Queue Implementation Using Array Min Heap

Min Priority Queue Implementation Using Array Min Heap:

The code is explained in comments. This code is implementation of min / minimum priority queue using min heap.

An easy to follow priority queue theory tutorial ( Max Priority Queue, Max Heap ) and with visualizations can be found here.

 Min Priority Queue Implementation C++:

 * @author  Quickgrid ( Asif Ahmed )
 * @link    https://quickgrid.wordpress.com
 * Code:    Min Priority Queue Implementation Using Array Min Heap

using namespace std;

#define N 100

struct node{
    char data;
    int key;
} A[N];

 * Initial heap size 0 as heap is empty
int heapsize = 0;

 * Find the parent node
int parent(int i){
    return ceil(i / 2.0 - 1);

 * Use for heap insert and decrease key
 * In if condition check if user attempted to increase value instead of decrease
 * Compare child with parent, if child is smaller then swap
 * Now mark that child and apply the same logic until it reaches root node
void decreaseKey(int i, node n){
    if(n.key > A[i].key){

    A[i] = n;
    while(i > 0 && A[parent(i)].key > A[i].key){
        std:: swap(A[i], A[parent(i)]);
        i = parent(i);

 * Search for a specific node to change its value
 * Returns the index the node being searched
int searchIndex(node n){
    for(int i = 0; i < heapsize; ++i){
        if(A[i].data == n.data)
            return i;
    return heapsize;

 * Called initially to create a min heap
 * Also called after a node extraction from min heap
 * Since the smallest value node is at the root of min heap
 * After extraction min heapify is called on root node
 * It compares parent with its children
 * If a smaller child found then its swapped with parent and
 * Min heapify is again called on that child to apply same procedure
void minHeapify(int i){
    int largest;

    int l = 2*i +1;

    if (l < heapsize && A[l].key < A[i].key)
        largest = l;
        largest = i;

    int r = 2*i +2;

    if (r < heapsize && A[r].key < A[largest].key)
        largest = r;

    if (largest != i){
        std::swap(A[i], A[largest]);

 * Does not extract any items only show the minimum element
node heapMinimum(){
    return A[0];

 * Increase heap size to create space for new node
 * Insert the node at that space by calling decrease key function
void heapInsert(node n){
    A[heapsize - 1].key = INT_MAX;
    decreaseKey(heapsize - 1, n);

 * Heap size less than zero mean no items in heap so nothing to extract
 * For min heap minimum value is at the root which in here is A[0]
 * Save the root and replace root with last element in the heap and decrease the heap size
 * So the root is still in the array in last position but no longer in the heap
 * Since the last element is now the root the heap may be unbalanced
 * So to balance the heap call min heapify on the root node again
 * Lastly return the saved root
node extractMin(){
    if(heapsize < 0)
        printf("Heap Underflow\n");

    node min = A[0];
    A[0] = A[heapsize - 1];
    return min;

 * Every time we extract heap size is automatically reduced
 * So no need change heap size in while loop
void printPriorityQueue(){
    printf("Main Output:\n");
        node ext = extractMin();
        printf("%c %d\n", ext.data, ext.key );

 * input data and key for node and insert that node in min priority queue
void inputQueueItems(){
    int i;
    printf("How many nodes?\n");
    scanf("%d", &i); getchar();
        node n;
        printf("Enter node name and its value:\n");
        scanf("%c%d", &n.data, &n.key);

int main(){


     * Sample input for quick testing
     * Before using this comment inputQueueItems() function call
    heapInsert({'b', 1});
    heapInsert({'e', 5});
    heapInsert({'d', 2});
    //decreaseKey( searchIndex({'a', 9}), {'a', 4} );

    return 0;

Leave a Reply

Please log in using one of these methods to post your comment:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s