Implement heap and priority queue with time complexity

heap-and-priority-queue
Spread the love

Heap and priority queue is a special Data structure in which is a complete binary tree. Or you can say heap is a tree-based data structure. There are two types of the heap, one is the max heap, and another one is this min-heap. The priority queue is an abstract data type similar to a regular queue or stack data structure in which each element additionally has a “priority” associated with it.

Read More: Implement Insertion Sort with Time complexity

heap-and-priority-queue
heap-and-priority-queue

Max Heap

In a max-heap, the key element at the root must be greater among the keys present at of its children. That means the root or parent element should be greater than its left and right child. Let’s look at this example.

  5 -> root
 / \
4->left   1 -> right

In this example, you can see the root element is greater than its left and right child.

Min Heap

In a min-heap, the key element at the root must be smaller among the keys present at of its children. That means the root or parent element should be smaller than its left and right child. Let’s look at this example.

  1 -> root
 / \
4->left   5 -> right

In this example, you can see the root element is smaller than its left and right child.

Let’s see the procedure of heap data structure. Well, to do that takes a couple of global variables and a few functions.

int A[100], n = 0;
void my_swap(int *a, int *b)
{
    int t = *a;
    *a = *b;
    *b = t;
}
int parent(int i)
{
    return i / 2;
}
int left(int i)
{
    return 2 * i;
}
int right(int i)
{
    return (2 * i) + 1;
}

Well, now I will show you how to implement the max-heap function. Look at this function, I will explain you below.

Implement Max Heap

void max_heap_insert(int val)
{
    n = n + 1;
    A[n] = val;
    int i = n;
    while (i > 1)
    {
        int p = parent(i);
        if (A[p] < A[i])
        {
            my_swap(&A[p], &A[i]);
            i = p;
        }
        else
        {
            break;
        }
    }
}

Well, you can see that this function takes a parameter. Now look inside this function, first, you have to increase n value one. Then store the value in the A[n] index. After then take another variable and assign n value. Well, now run a while loop until i is greater than 1. Inside the loop store the parent of i’th index, you can get it using the parent function. Now check a condition, if A[p] < A[i] then swap these values and reassign I value is p. Else portion return break.

Implement Min Heap

void min_heap_insert(int val)
{
    n = n + 1;
    A[n] = val;
    int i = n;
    while (i > 1)
    {
        int p = parent(i);
        if (A[p] > A[i]) // Change
        {
            my_swap(&A[p], &A[i]);
            i = p;
        }
        else
        {
            break;
        }
    }
}

max-heap and min-heap are the same just a small change. You may notice, I already marked it. A[p] > A[i]

The time complexity for cases is O(logn).

Print Heap Value

void print_heap(int A[], int heap_size)
{
    cout << endl;
    if (n == 0)
    {
        cout << "Empty Heap!!\n";
    }
    for (int i = 1; i <= heap_size; i++)
    {
        cout << A[i] << " ";
    }
}

Using this function you are able to print heap’s data. It’s a simple function that takes O(n) time complexity.

Remove max heap value

int delete_max_heap()
{
    if (n == 0)
    {
        return -1;
    }
    int val = A[1];
    int temp = A[n];
    n--;
    int i = 1;
    A[i] = temp;
    while (i < n)
    {
        int l = left(i);
        int r = right(i);
        if (A[i] < A[l])
        {
            my_swap(&A[i], &A[l]);
            i = l;
        }
        else if (A[i] < A[r])
        {
            my_swap(&A[i], &A[l]);
            i = r;
        }
        else
        {
            break;
        }
    }

    return val;
}

When we insert data in heap we have to check from bottom to top. Implement the delete method we have to check from top to bottom. Look at this function, First, I check a condition for the heap is empty or not. Well, after I took two variables and assign the first and last index’s value. Then reassign the first index’s value with the last index’s value. As well as I decreased the n value and execute a loop from 1 to n.

Inside the loop, I stored the left and right indexes using the left and right functions that I have defined before. Well now check a condition like the insert function and swap values. Finally, return the value of A[1] that I’ve isolated before.

Remove Min heap value

int delete_min_heap()
{
    if (n == 0)
    {
        return -1;
    }
    int val = A[1];
    int temp = A[n];
    n--;
    int i = 1;
    A[i] = temp;
    while (i < n)
    {
        int l = left(i);
        int r = right(i);
        if (A[i] > A[l])
        {
            my_swap(&A[i], &A[l]);
            i = l;
        }
        else if (A[i] > A[r])
        {
            my_swap(&A[i], &A[l]);
            i = r;
        }
        else
        {
            break;
        }
    }

    return val;
}

Delete min-heap value is the same as max-heap deletion. The time complexity of these functions is O(logn).

Well, now you may call this function in the main function like below.

int main()
{
    print_heap(A, n);

    int arr[] = {1,
                 3,
                 5,
                 4,
                 6};
    for (int i = 0; i < 5; i++)
    {
        min_heap_insert(arr[i]);
    }
    print_heap(A, n); // 6 5 3 1 4
    cout << delete_max_heap(); 6 
    print_heap(A, n); 5 4 3 1
    return 0;
}

Full code of heap and priority queue

#include <bits/stdc++.h>
using namespace std;
int A[100], n = 0;
void my_swap(int *a, int *b)
{
    int t = *a;
    *a = *b;
    *b = t;
}
int parent(int i)
{
    return i / 2;
}
int left(int i)
{
    return 2 * i;
}
int right(int i)
{
    return (2 * i) + 1;
}
void min_heap_insert(int val)
{
    n = n + 1;
    A[n] = val;
    int i = n;
    while (i > 1)
    {
        int p = parent(i);
        if (A[p] > A[i])
        {
            my_swap(&A[p], &A[i]);
            i = p;
        }
        else
        {
            break;
        }
    }
}
void max_heap_insert(int val)
{
    n = n + 1;
    A[n] = val;
    int i = n;
    while (i > 1)
    {
        int p = parent(i);
        if (A[p] < A[i])
        {
            my_swap(&A[p], &A[i]);
            i = p;
        }
        else
        {
            break;
        }
    }
}
void print_heap(int A[], int heap_size)
{
    cout << endl;
    if (n == 0)
    {
        cout << "Empty Heap!!\n";
    }
    for (int i = 1; i <= heap_size; i++)
    {
        cout << A[i] << " ";
    }
}

int delete_max_heap()
{
    if (n == 0)
    {
        return -1;
    }
    int val = A[1];
    int temp = A[n];
    n--;
    int i = 1;
    A[i] = temp;
    while (i < n)
    {
        int l = left(i);
        int r = right(i);
        if (A[i] < A[l])
        {
            my_swap(&A[i], &A[l]);
            i = l;
        }
        else if (A[i] < A[r])
        {
            my_swap(&A[i], &A[l]);
            i = r;
        }
        else
        {
            break;
        }
    }

    return val;
}

int delete_min_heap()
{
    if (n == 0)
    {
        return -1;
    }
    int val = A[1];
    int temp = A[n];
    n--;
    int i = 1;
    A[i] = temp;
    while (i < n)
    {
        int l = left(i);
        int r = right(i);
        if (A[i] > A[l])
        {
            my_swap(&A[i], &A[l]);
            i = l;
        }
        else if (A[i] > A[r])
        {
            my_swap(&A[i], &A[l]);
            i = r;
        }
        else
        {
            break;
        }
    }

    return val;
}
int peek()
{
    return A[1];
}
int main()
{
    print_heap(A, n);

    int arr[] = {1,
                 3,
                 5,
                 4,
                 6};
    for (int i = 0; i < 5; i++)
    {
        min_heap_insert(arr[i]);
    }
    print_heap(A, n);
    // cout << delete_max_heap();
    print_heap(A, n);
    return 0;
}

Spread the love

About Anisur Rahman Shahin

Hello. My name is Shahin. I'm a tech enthusiast guy. Personally, I’m an Optimistic and always in hurry kinda person. I'm a freelance web developer. I am working at Zakir Soft as Laravel Developer. My Portfolio website: https://tutspack.com

View all posts by Anisur Rahman Shahin →

Leave a Reply

Your email address will not be published.