Implementation Of Heap Data Structure In C++ Using Array.

By Ashwini Laxman Jadhav

In this tutorial, We will learn the implementation of heap data structure using an array. It involves insert(), extract(), searching() and other functions.

In this tutorial, we will take a brief introduction to heaps. basically, heap structure is implemented using binary tree rules. But heaps themselves have two parts a] Minheap b] Maxheap. In this tutorial, we are implementing the program for minheap.

MinHeap Implementation In C++ Using Array's.

a]Minheap:- 

 Minheap is implemented by using some rules that its parent node must have a smaller value than its child node and vice versa for its subchilds.

Example:-

                                               2

                                          /         \

                                       3              6

                                   /       \        /      \

                                 4          5    8          9

b]Maxheap:-

Maxheap is implemented by using some rules that its parent node must have a max value than its child node and wise versa for its subchilds.

Example:- 

                                                   9

                                              /          \

                                           7                8

                                       /      \           /       \

                                   5           6       4            2

In the insert function, you need to follow the following logic for implementing minheap:-

Logic:-

  -  firstly you need to check whether your minheap is full or not.

  -  if it is not full then we are making heap size to follow the first index of are minheap.

  -  check I!=0 and the element present at the parent position is greater than the child element

       - if this condition is true then we need to swap the element to make are minheap.

 

In the extract min function, you need to follow the following logic for implementing minheap:-

Extract min is the function used to extract the element from the minheap.

Logic:-

 - check whether the minheap has any element or not

 - check if the minheap has only one element.

    if yes, then decrease the size of your minheap.  

 - assign the root node and decrease the size of your minheap and call the heapify function.

So, if you want the whole source code of this minheap data structure then download the file from the download section.