Implementation of Max Heap in C++

A max heap is a tree-based data structure that satisfies the property of a heap. For every node, i in the max heap other than the root, the value of that node is less than or equal to the value of its parent. Each root node in a max heap can have almost two child nodes where the value of the child nodes must be less than or equal to its parent node. To implement max heap in C++ we use the array data structure. For any node at the index i in the array, the relationship between the parent and child nodes are as follows:

• Index of Parent Node: (i – 1) / 2
• Index of the Left child Node: 2 * i + 1
• Index of the Right child Node: 2 * i + 2

Representation of Max Heap in C++

To represent a max heap efficiently, we can use a class instead of an array because for an array we will have to maintain separate variables to keep track of the size of the heap. Using a class we can encapsulate all of the heap data members and operations within a single class. We will use template instead of a specific data type for the max heap so that it can support multiple types of data. The MaxHeap class will consist of the following data members:

template <typename T>
class MaxHeap {
    vector<T> array;  
    int size;         
    int capacity;     
};

here:

• array: is a std::vector that will store the max heap elements.
• size: denotes the current number of elements present in the max heap.
• capacity: denote the maximum number of elements the max heap can hold.
• T: denotes the type of data the max heap will hold.

The following diagram represents how the index of each element in a max heap is mapped within the array:

Explanation: For the above max heap the root node 15 of the max heap is present at the 0th index of the array,and it’s left and right child 5 and 10 are present at 2*i+1 and 2*i+2 indices that is at index 1 and 2. Similary the other nodes of the max heap are represented in the array using the same approach.

A max heap is defined as a complete binary tree where every node’s value is at least as large as the values of its children. This makes it useful for implementing priority queues, where the highest priority element is always at the root. In this article, we will learn how to implement the max heap data structure in C++.