One of the advantages of being raised in India is to experience the beautiful Indian Market! Apart from the chaotic environment, where every seller struggling to draw the attention of every buyer towards the direction of his display which may be accompanied by shoutings and music, one distinct thing that probably everyone is familiar with, is how these sellers display their stuff. Whether it is a fruit, or a vegetable, or a piece of cloth, these sellers manage to put them all in a heap.

For example, look at this old woman, and how she heaped all the coconuts:

And how the shopkeeper heaped literally everything they sell:

Looks tidy and attractive right? Well, to me (being the most unorganized person in my family history), YES! So to these shops, making heaps are an integral part of the business. Well if that does not attract you to these heaps already, I must say heaps are a necessary part of any computer science (with Algorithms and Data Structure) syllabus. But don't worry, this article will not be the same as those in your book, instead, we will be taking real-world examples to understand the same.

Now that you have a basic idea of how heap looks in the real world, we will soon be talking about how it looks in the Computer Science World! But before doing that, you need to understand Trees.

Trees

Ah, I can hear you saying "Wait, what? Trees? Hey dude, look, I'm not a kid okay, I..", yep we all know what a tree is, but, you know, we "CompSci-geeks" are weird, so we would not be talking about normal trees we see in day to day lives. Well, by "trees", "normal humans" tends to imagine this:

But we are not normal humans, right? We are the "CompSci-geeks"! So, to us, trees mean this:

(An inverted tree basically). The branches are called "edges" and the points where the branches divide or end, we call them "Nodes". The nodes that give birth to other nodes under them is called a "parent node" and its children are simply called "daughter node" or "children nodes". The main stem of the tree is called "root node". To understand better, I have circled out the parts which we call a "node" in the picture below:

So in computer science, Tree is a "non-linear" hierarchical data structure that stores the information naturally in the form of a hierarchy style. It represents the nodes connected by edges. Cool.

Now that we are familiar with "Trees", let us talk about a special type of tree called "Binary Tree".

Binary Trees

"Oh God, now whats a binary tree?", well, a binary tree is more simple than you think how it is. A Binary tree is a tree wherein every parent node has two children. Let us understand this by Mike's weird family.

Mike is a cute looking bacteria (umm, bacterias because we're too tired with humans already), he has got a sister called Juliett. Mike and Juliett's father, Mr. Charlie also has a sibling, Mr. Romeo who has two children Bravo and Foxtrot, and both Mr. Charlie and Mr. Romeo share a single father Mr. Alpha. So here's how Mike's Family tree looks like:

So you see, the good old Mr. Alpha (or the "root node" of the tree) has got two children and who in turn has got two children too. Such types of trees are called "Binary Trees". And here's a fun thing, you can call Mike as the "left child" of Mr. Charlie and Juliett as the "right child". Similarly, Mr. Charlie is "left child" and Mr. Romeo is the "right child" of Mr. Alpha.

So we got to remember this important thing: A tree is a binary tree where every parent node of the tree have at most two children.

Array Representation of a Binary tree

Well, so Mr. Alpha bought gold bars for his children and grandchildren, and since he is old, he thought to divide them into his family. So he has set some family rules for his children and grandchildren. The rules might look a bit on the tough side for you, but believe me, it is super simple. 

Mr. Alpha loves gold, so he would like to keep one for himself too. Then he made a weird rule that children on the left side of his family tree should get the most preference while dividing the bars. If any child or children is missing on the left side of his family then his part of the gold should be kept preserved until he comes and takes it, whereas if any child or children is missing on the right side of his family, then the gold should not be preserved, and will either be sold or given to someone else. 

Also, generations nearer to his generation shall get the gold first. I know I know... This is confusing. Let us understand this with a set of pictures.

So here's how the gold bars look like:

Now, Mr. Alpha thought to write names on the bars so that everyone should know which bar belongs to whom. So here's how it looks after the bar is marked and divided:

Look how Mr. Alpha gave preference according to his conditions:

1) Mr. Alpha kept a gold bar for himself.

2) The generations closer to him (in this case his direct children) got the gold bars first.

3) The children on the left side of the family tree are given the gold bars first. The child at the rightmost side of this family tree, i.e. Foxtrot got the gold bar at the end.

Now, let's say if Mike and Juliett gets missing, and the family tree looks like this:

Then the gold bars for Mike and Juliet would simply be preserved until they come back and claim for it. So here is how it will look:

Now, let's say Mike and Juliett came back, but Bravo and Foxtrot went missing, then the gold bars for them would simply be sold. Here's how it would look:

Now let me say all these in the languages of computer science. If you have to represent a binary tree in the form of an array, so you'll fill the array according to the levels of the binary tree i.e., one level (or generation from the above example) at a time. First, you'd fill the root element and then its children nodes. While filling you should remember that you will start filling from the leftmost node of a level and gradually proceed to the rightmost node. If you find a node missing but there is a node on the right to it, keep a blank space for that node. But if there is no right node, do not keep any space and go to the next level if any.

Finding the parent and children of a node

So, Mr. Alpha's children and grandchildren are forgetful, so they often forget who their parents are (yes, how weird!), so being a faithful friend of Mr. Alpha, Mr. Oscar derived some formula for them so that they can find out their parents quickly.

Mr. Oscar asked to represent the family as an array first. Then if the bacteria, who forgot who's their parent is, at index "i" in the array then:

• It's left child is at: 

  2 × i

• It's right child is at: 

  ( 2 × i ) + 1

• It's parent is at: 

  [ i / 2 ]           (Remember! you must not take any decimal or fractional numbers. If its a decimal, just throw the digits after the decimal point away.)

Well, there are a lot more topics to cover under binary trees but to keep this article simple and since it is just a basic introduction to trees and heaps, we will end the trees here and move to heaps instead.

Heaps

From the introduction of the article, you must have got an idea of what heaps are in the real world. Now we shall discuss it in the "Computer Science World"!.

In the languages of computer science, Heap is a binary tree-based data structure. So, each node in heap will have at most two daughter nodes.

Heaps are of two types, Min Heap and Max Heap.

Max Heap

If we look at Mike's family tree, and consider the ages, well, of course, Mr. Alpha will be older than all. Mr. Charlie is Mr. Alpha's first child, so he is the second oldest in the family tree. Then comes Mr. Romeo, Mike, Juliett, Bravo, and Foxtrot. So you see, every child is less old than its parents. A max heap is a heap where the "key" of every node of the heap is less the key of its parent node. The "key" of a node basically means the component we are using to compare with other nodes, so in this case, the "key" is the age.

So, here, the following heap is a max heap:

You must be guessing, 16 is greater than 15, so basically Foxtrot is elder than Mike, so why is the tree so? You see the key (the age, in this case) must be less than the key of the parent node. So this condition is satisfied, hence its a max tree.

Min Heap

Opposite to max heap, the key of the parent node must be less than the key of the daughter nodes. So, let us consider the price of mobile phones Mr. Alpha's family use. So we will make the key as the "price of the mobile phones". 

Mr. Alpha being the oldest bacteria, uses a mobile phone that costs the least, maybe a Nokia 3310 XD, because he does not understand so much in mobile phones. His children use a mobile phone that costs neither too high, nor too low. but Mike and his sibling and cousins are gamers so they require a mobile phone of good specifications. So, in this case, the Heap would look like:

You see, the key of every node is less than the key of its parent node. Hence it is a min-heap.

Conclusion

A Tree in computer science is a "non-linear" hierarchical data structure that stores the information naturally in the form of a hierarchy style. It represents the nodes connected by edges. A tree where every node has at most two daughter nodes, is called a binary tree. A binary tree is a tree where the key of any node is less than the key of its parent node, is called a Max heap and A binary tree where the key of any node is more than the key of its parent node, is called a min-heap.

That's all for this article, we will be bringing more articles like this so make sure you check our page every day. 

Have doubts? Write them here.

Know these already? Wow! Well, we are looking to expand our team, check here.

Want to contact us? Send us a mail at hello@icrewsystems.com.