Implementing Heaps In C++

Filed Under: C++
Heap Implementation In C

What are priority queues or heaps in C++? We already have various data structures to store our data but what’s so special about heaps? In this article, we will look at the answers to these questions. We will further try to understand the implementation of heaps in C++. So let’s start with the motivation to implement heaps.

Why Implement Heaps in C++?

Whenever we need to find the minimum or the maximum element among some given number of elements say N, we employ heaps for this purpose. The reason is very simple, heaps do this work in minimum possible time complexity and resources.

The table given below compares the space and time complexities of different data structures for basic operations.

OperationVectorSorted ArrayBSTHeap
Insert/PushO(1)O(N)O(Height)O(Log2N)
PopO(N)O(1)O(Height)O(Log2N)
GetO(1)O(1)O(Height)O(Log2N)
Time Complexity Comparision Of Various Data Structures

As you can clearly notice that the heap offers the best time complexity for all the operations. This accounts for the need for heaps.

What Is A Heap?

A heap is a data structure that stores the minimum or the maximum element at the top of the heap based on its type. A heap can be of two types, it can either be a min-heap or a max-heap. A min-heap gives nearly constant time access to the minimum element among all the elements at any point in time. A max-heap differs in the sense that it gives access to the maximum element among all the elements.

Note: A heap is a complete binary tree. This is the reason why we can represent heaps as arrays(A complete binary tree can be represented as an array).

Heap Order Property: Every parent > Children: Max-Heap

Heap Order Property: Every child > Parent: Min-Heap

Representation Of Heaps As Arrays

Though heaps are visualized as non-linear data structures but in practice, we use arrays to implement heaps. A simple visualization of a heap using an array is given below.

Heap Representation Implementing Heaps In C++
Heap Representation

Each child node is related to the parent node by the following relation.

right_child = 2*parent

left_child = 2*parent + 1

Note: This relation is valid when the indexing is 1 based.

Implementing Heaps In C++

Let’s now move on towards the heap implementation in C++. The implementation will be in two steps, in the first step we’ll learn to insert an element in the heap. Later we’ll implement the function for the removal of elements

Create a Custom Heap Class

class Heap
{
        vector <int> v; // array to store the data
        bool min_heap; // by default we will generate a min_heap
public:
        // constructor
        Heap(int default_size = 10, bool type = true)
        {
                v.reserve(default_size);
                v.push_back(-1); // to block the 0th index
                min_heap = type;
        }

        //custom comparator function
        bool compare(int a, int b)
        {       
                if(min_heap)
                        return a < b;
                return a > b;
        }
};

Insertion In Heaps (Min Heap)

Step 1: To insert an element in the tree, we insert the element at the end of the array. But later we will change the position of the element to satisfy the heap order property.

Inserting 30 In The Heap Implementing Heaps In C++
Inserting 30 In The Heap

Step 2: We will compare the data of the node with the parent node. If parent > children, we will swap their values.

1st Comparision
1st Comparision

Step 3: But step 2 will disturb the ordering of the nodes on top of it. To solve this problem, we will repeat the same process till we hit the root node.

2nd Comparision
2nd Comparision

C++ Code For Insertion in Heaps

        // function to insert an element in the heap
        void push(int data)
        {
                v.push_back(data);
                int index = v.size() - 1; // index of the last pushed element
                int parent = index/2;

                //while loop to run till every node of the heap is fixed
                while(index > 1 && compare(v[index], v[parent]))
                {
                        // if the heap order property is not satisfied, swap the elements
                        swap(v[index], v[parent]);
                        index = parent; // change the index of the child
                        parent /= 2;
                }
        }

Removing Min/Max Element From Helps in C++

The minimum/maximum element is always present at the top depending upon the type of the heap. When we remove this element, the heap order property is disturbed. Now a new minimum/maximum element is to be shifted to the top. So let’s move on to the implementation of the pop function in a heap.

Removing Topmost Element From The Heap
Removing The Topmost Element From The Heap

Step 1: You can not break the tree from the root. Swap the first(topmost) element of the array and swap it with the last element. So that we can remove the element from the end of the array.

Swapping The Topmost And The Last Element
Swapping The Topmost And The Last Element

Step 2: Shrink the array from the end. Now the heap order property will get disturbed because of the shifting of the last element to the front. To restore the heap order property once again, we will develop a function heapify(). This function will fix the tree recursively until all the nodes satisfy the heap order property.

Deletion Successful Now Regenerate The Ordering
Deletion Successful Now Regenerate The Ordering
1st Comparision 1
1st Comparision 1
2nd Comparision Notice That The Heap Property Is Regenerated
2nd Comparision Notice That The Heap Property Is Regenerated

Code For Extraction Of The Topmost Element from Heaps in C++

        void heapify(int index)
        {
                int min_index = index;
                int left = 2 * index;
                int right = left + 1;
                int last = v.size() - 1;

                // both the children should have the value between
                // 1 <= child <= last
                if(left <= last && compare(v[left], v[index]))
                        min_index = left;
                if(right <= last && compare(v[right], v[index]))
                        min_index = right;

                if(min_index != index)
                {
                        swap(v[index], v[min_index]);
                        heapify(min_index);
                }
        }

        void pop()
        {
                int last = v.size() - 1;
                swap(v[1], v[last]);
                v.pop_back();
                heapify(1);
        }

Time Complexity Analysis

Note: The height of a complete binary tree is: O(Log2N).

Insertion

We start by inserting the new element at the end and later we push it upwards until all the nodes are fixed. This operation can take at most Log2N iterations since each time the value of the index of the parent becomes half of the previous value.

Complexity: O(Log2N)

Heapify

The comparison starts from the index of the given node, in the worst case the index passed as the argument can be the first index. This means that the element can move at most Log2N steps downwards.

Complexity: O(Log2N)

Deletion

Each deletion operation swaps the first and the last element in the vector, and later calls the heapify() operation on the root

Complexity: O(Log2N)

Conclusion

Let’s conclude this article by recalling what we discussed today. At first, we looked at the need for heaps. Heaps are very powerful data structures that offer nearly constant time access to the minimum/maximum element at any point in time. We further learned the representation, insertion of an element, and deletion of an element from a heap. In the end, we proved the time complexity of various operations associated with heaps.

References

To learn more about heaps, you can visit the following websites.

https://en.cppreference.com/w/cpp/algorithm/make_heap

https://en.wikipedia.org/wiki/Heap_(data_structure)

close
Generic selectors
Exact matches only
Search in title
Search in content