Search Algorithm in C++ || Minheap

What is a Binary Heap?

A heap is always (logically) a complete binary tree. It has these basic properties:

• All levels are full except possibly the last level
• If the last level is not full, it is left justified 
• It has the either of these two Heap properties in case of
• Min Heap: Each Parent key <= Both Children Keys (Root is minimum)
• Max Heap: Each Parent key >= Both Childen Keys (Root is maximum)

For now, we will focus on Min Heap.

Min Heap

As stated above, min heap will have minimum of all the keys at the top due its heap property. 

For instance, look at the tree in Fig(1.1): the root node which contains 2 is the smallest. Similarly, all the elements on level 2 are smaller then those on level 3 and so on. Observe that there is no order between the left and right children of a key i.e. it doesn't matter if left child > right child or vice versa. They are just compared to their parent key (min heap property).

Fig: 1.1

Now, to move onto the code of the Min Heap:

There are three basic functions:

int lchild(int i)    //returns the index 
{
return (2 * i);
}

int rchild(int i)
{
return ((2 * i) + 1);
}

int parent(int i)
{
return (i / 2);
}

I have implemented Min Heap using Templates. Also, I have used the default Vector class to stored keys.


template <class T>
class minHeap {
private:

vector <T> h; //using default vector class
....
}

To insert an element,

void insert(const T & temp)
{

h.push_back(temp);  //default insert method for the vector class
int i = size();
while (i > 1 && h[parent(i)].fc > h[i].fc)   //Not root && parent & child comparison
{
swap(h[parent(i)], h[i]);
i = parent(i);
}
}

And for deleting a node:

void deMin()
{
if (size() > 0)
{
swap(h[1], h[size()]);
h.pop_back();     //deleting the last element
minheapify(1);
}
}

After deletion, we shall have to MinHeapify the whole tree so that the order is mainted.

void minheapify(int i )     //percolate down
{
int lc = lchild(i);  //left child index
int rc = rchild(i);  //right child index
int imin = i;        //min index
if (lc < size() && h[lc].fc < h[imin].fc)   
imin = lc;

if (rc < size() && h[rc].fc < h[imin].fc)
imin = rc;

if (i != imin) //parents/current isn't imin itself
{
swap(h[i], h[imin]);
minheapify(imin);     //recursive call
}

}

What minheapify does is that it takes the node/key at index i (given as input to the function) and checks if the key is greater than any of its children (a violation of Min Heap Property), if any such key is found, it's index is stored in imin and then, node i and imin are swapped. If no such key is found (no violation of minheap property), Heapify stops or else it continues by now passing imin as input in the self recursive call to MinHeapify().

You can create helper functions of your own to getNode(), find() and so on. I have provided the basic functions :P


Thank you for reading! I hope it helped! :)
If any questions, comment below!