Heap data structure (minheap and maxheap examples)

Heap is physically an array-like storage data structure whereas virtually we can see this as a binary tree. In heap data structure the element in the 0th index represents as the root of the tree and its children indices are calculated using the below formula.

left child = 2 * rootIndex + 1
right child = 2 * rootIndex + 2

Example of Heap

Let’s take a heap example that has integer elements like {3, 8, 5, 10, -9, 4, -3}.

Physically these elements are stored in an array as showing below.

array representation of heap.

Whereas this heap can virtually represent a binary tree where index0 as the root node. This is showing in the below diagram.

heap virtual representation.

As showing in the above picture in a heap binary tree, a node is either minimum or maximum than its child nodes. If the root node is maximum than its child nodes then it is called Max Heap whereas if the root is minimum than its child nodes then it is called Min Heap.

Types of Heap

  1. Min Heap
  2. Max Heap

Min Heap

As discussed earlier a Min Heap where all child nodes of a root node is greater. In the above picture nodes 8, 5 are greater than their root node 3.

To generate a min-heap from an input array, we have to check the minimum of each child of the given input and if the root is not minimum then we need to swap the minimum element with root and do the same for newly swapped child element. This is what we call as MinHeapify (in programming terms).

Let’s see the coding part of the MinHeapify

void Heap::minHeapify(int atIdx)
{
    int minIdx = atIdx;
    int leftIdx = left(atIdx);
    int rightIdx = right(atIdx);
    if (leftIdx < size && inpArr[minIdx] > inpArr[leftIdx])
    {
        minIdx = leftIdx;
    }
    if (rightIdx < size && inpArr[minIdx] > inpArr[rightIdx])
    {
        minIdx = rightIdx;
    }
    if (minIdx != atIdx)
    {
        swap(inpArr[atIdx], inpArr[minIdx]);
        minHeapify(minIdx);
    }
}

Complexity: O(logN)

This code re-arranges the heap whenever there is a new element coming to it, to satisfy min-heap property.

Max Heap

Max heap is a heap in which all child nodes are lesser than the parent node. Let’s see below max heap array.

max heap array representation.

Let’s see the same max heap in a binary tree representation.

a max-heap with root 10.

As we learn in min heap here we have to bring maximum number as parent in each level. Let’s see the code part of the MaxHeapify.

void Heap::maxHeapify(int atIdx)
{
    int maxIdx = atIdx;
    int leftIdx = left(atIdx);
    int rightIdx = right(atIdx);
    if (leftIdx < size && inpArr[maxIdx] < inpArr[leftIdx])
    {
        maxIdx = leftIdx;
    }
    if (rightIdx < size && inpArr[maxIdx] < inpArr[rightIdx])
    {
        maxIdx = rightIdx;
    }
    if (maxIdx != atIdx)
    {
        swap(inpArr[maxIdx], inpArr[atIdx]);
        maxHeapify(maxIdx);
    }
}

Complexity: O(logN)

Now let’s see complete code with insert, minimum and maximum operations on this heap data structure in below gist.

// Output
Maximum value in lowest 5 values in heap: 10

Complexity of both min-heapify and max-heapify is: O(logN)

This is all about the heap data structure along with min-heap and max-heap. If you know any better approach to solve this problem, please let our readers know by commenting here below. Happy Learning!.