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!

Read More

Search Algorithms in C++ || Binary Search Tree || Part 3

This is part 3 for Binary Search Tree, previous posts are Part 1 and Part 2. In this post, I'll attach the complete code also explain how Remove function for BST can be implemented.

There are a few situations possible while removing a node from the BST. There node may have no children, both children, etc. Let's have a quick view of them.

Key is element to be deleted.

• BST is empty -- then do nothing.
• Key is not found -- do nothing.
• Key is found at a node which is:

                 (a) A leaf node -- delete that node (let's call it current node), Update its Parent's appropriate child to Null (e.g. if it was Left child that got deleted, set lChild pointer in Parent to null.), point Previous (Previous is the Parent node of the Current node) pointer to null. (if the current was leaf as well as root, then set root pointer to null)

                (b) Not a leaf node and has:

                       (i) One child N -- Previous adapts N, Remove Current

                       (ii) Two children -- find the Predecessor¹ P of the current node, Swap P and current node, if P is leaf then apply A else apply B(a)

Figure A

Figure B

 ¹To find a Predecessor, go to left child and then keep going right till the leaf element is reached. Predecessor is the element which is smaller to the Current node but larger than all it's left side children.

In this figure A, you can see even if replace predecessor with current node i.e. 12 with 9, the order of the tree remains intact. See figure B. 

Now let's look at the code.

void remove(const T & key)

{

if (s == 0)

{

cout << "\n Empty! \n";

return;

}

else

{

if (search(key) == false)

{

cout << "\n Key not found! \n";

return;

}

//SEARCHING

Node* curr = root;

Node* prev = nullptr;   //parent

while (curr != nullptr && curr->data != key)

{

prev = curr;

if (curr->data > key)

curr = curr->lchild;   //key is smaller

else

curr = curr->rchild;   //key is greater

}    

if (curr->lchild == nullptr && curr->rchild == nullptr) //if leaf

{

delete curr;

if (curr == root)

root = nullptr;

//is it left or right child?

else if (prev->data > key)   

prev->lchild = nullptr;

else if (prev->data < key)

prev->rchild = nullptr;

}

else     //not leaf

{

//single child

if ((curr->lchild != nullptr && curr->rchild == nullptr) || (curr->lchild == nullptr && curr->rchild != nullptr))

{

if (prev->lchild = curr)    //if curr was left child of its parent

{

if (curr->lchild != nullptr) //if curr has left child

{

prev->lchild = curr->lchild;    //prev adopts left child

}

else if (curr->rchild != nullptr)  //if curr has right child

{

prev->lchild = curr->rchild;   //prev adopts right child

}

}

else if (prev->rchild = curr)    //if curr was right child of its parent

{

if (curr->lchild != nullptr) //if curr has left child

{

prev->rchild = curr->lchild;    //prev adopts left child

}

else if (curr->rchild != nullptr)  //if curr has right child

{

prev->rchild = curr->rchild;   //prev adopts right child

}

}

delete curr;

}

//if curr has 2 children

else if (curr->lchild != nullptr && curr->rchild != nullptr)

{

//find the predecessor

Node* curr2 = curr->lchild;  //go to left of the curr

Node* prev2 = curr;

Node* prev3 = nullptr;

while (curr2 != nullptr)

{

prev3 = prev2;

prev2 = curr2;

curr2 = curr2->rchild;

}

swap(curr->data, prev2->data);   //swapped

//if prev2 is a leaf

if (prev2->lchild == nullptr && prev2->rchild == nullptr) 

{

if (prev2 == root)

root = nullptr;

else if (prev3->lchild == prev2)

prev3->lchild = nullptr;

else if (prev3->rchild == prev2)

prev3->rchild = nullptr;

delete prev2;

}

//if prev2 has one child

else if ((prev2->lchild != nullptr && prev2->rchild == nullptr) || (prev2->lchild == nullptr && prev2->rchild != nullptr))

{

if (prev3->lchild = prev2)    //if prev2 was left child of its parent

{

if (prev2->lchild != nullptr) //if curr has left child

{

prev3->lchild = prev2->lchild;    //prev adopts left child

}

else if (prev2->rchild != nullptr)  //if curr has right child

{

prev3->lchild = prev2->rchild;   //prev adopts right child

}

}

else if (prev3->rchild = prev2)    //if prev2 was right child of its parent

{

if (prev2->lchild != nullptr) //if curr has left child

{

prev3->rchild = prev2->lchild;    //prev adopts left child

}

else if (prev2->rchild != nullptr)  //if prev2 has right child

{

prev3->rchild = prev2->rchild;   //prev adopts right child

}

}

delete curr;

}

}

}

s--;   //reducing size

}

}

This is all so far about BST. 

To download code, Click Here!

In my code, I have other utility functions too as per my requirement which I have not discussed here. Keep them or remove them, your choice! :P

Thanks for reading. If any question, Comment below! :)

        

Read More

Search Algorithms || Binary Search Tree || Part 1

What are Search Algorithms?

Search Algorithms provide us with fast search mechanism. Not only search, but insertion and deletion also becomes faster. These sort of Algorithms are normally explored under the subject Data Structures. There are different algorithms like binary search, binary search tree, minHeap, etc. 

In this post and some upcoming posts, I'll be explaining Binary Search Tree. So let's begin.

Binary Search Tree

In binary search tree, the data is divided into halves and there is a root element. There are nodes in the tree. 

• Each node has zero, one or two children. 
• Each node has only one parent. But may have grand parents, great grant parents and so on :P
• Nodes that have zero children are called leaves.
• Each tree has a height, which is number of jumps/edges from the root to the most distant leaf.
• Similarly, height of a node is the number of jumps/edges from the node to most distant leaf.

Height of the root is the height of the tree.

In the image given above, you can observe a binary tree. The height of this tree is 2. Root has two children, right and left children. The right child of the root has only one child i.e. a left child. While the left child of the root has two children which is the maximum number of children a node can have. The blue nodes are the leaves of these tree. 

A tree may not necessarily have all the leaves at the same level e.g.

in the image on the right. In this image, there are still 3 leaves i.e. 2 blue nodes and the right child of the root.

The data in a binary tree is sorted, for instance, let's take a binary tree that stores integers in the nodes. On the left of the root, there will be integers smaller than the root and on the right there will be integers larger than the root. In other words, the left child of a node is smaller than itself and the right one is greater than itself.

In this image, the root contains integer 12. All the integers to the left of the root are smaller than 12. Similarly, the numbers to the right are larger than 12. In the second row, consider node 8. Which has left child containing number 5 (smaller than 8) and right child containing 9 (larger than 8).

Categories on the basis of arrangement of the nodes

Perfectly Balanced Tree : A tree which has equal number of nodes on the both sides of the root.

Skewed BST : A tree which doesn't have equal number of nodes on both sides of the root. A tree may be left or right skewed.

The height of a tree is
                                              h = lg(n+1) - 1

where,
h : height of the tree
lg : log base 2
n : number of nodes


In the next post, I'll explain a BST with a code example. 👍
Thank you for reading and if any questions, comment below! 😊😇

Read More