Max Heap Create and Sorting

Hi, this is Shubham Mishra. I write blogs on algorithms and new technologies. In today's blog, we will going to cover the max heap topic. Now before actually looking the code lets understand the max heap tree.

A complete binary tree is a tree in which every levels are completely filled except the lowest one, which is filled from the left. And A max heap is a complete binary tree and the root node always have the max value of the tree, hence the name is max heap. Now with this max heap tree is have one more important property, the value of a node is always greater than or equal to the all chindren nodes. Confused, let me explain with a diagram:

As can be seen in above tree, this is complete binary tree, since nodes are entered in such as way that all of the in between nodes are have 2 childrens. And any node's value is any time greater than all the children nodes. Take 6, it is greater than all the child nodes (5 -> 4, 2 And 3 -> 1). Similar to this 5 is greater than 4 and 2.

Now since we understood the max heap tree and its rules, let jump on its presentation with an Data structure. So since in max heap tree no in between space is wasted we atually use Array for the representation of max heap tree. The root element is Arr[1], actually Arr[0] stores the number of nodes in the tree. Now very important,

• -> Arr[(i-1)/2] Returns the parent node.
• -> Arr[(2*i)+1] Returns the left child node.
• -> Arr[(2*i)+2] Returns the right child node.

Array [ number of nodes count, Root node, 2nd node, 3rd node, ...., last node]

Now u may say how can u confident about above mathmatical expression,

via GIPHY

so as explained above the max heap tree is complete binary tree, so any time entering a new node will always be in such as way that no inbetween space is wasted and inserted with the care that tree should be complete.

The important usage of this tree is for sorting, since the root node will contain the max element so when root element is removed it is replaced by the next max value.

Now lets jump on the code section, (This code is in ruby language)

this code snippet have few functions as,

Creation part

• create_max_heap : Is to initialize the tree
• heap_insert : Is to insert the node one at a time
• upadjust : While inserting the new node, it should be upadjusted so that the ending tree should fullfill all the rules of max heap tree

Sorted array generation Now to get the sorted array, each time root node is poped and the tree is downadjusted so that at the end tree follow all the rules of max heap tree

• get_sorted : Function to get the sorted array
• ger_max : Is to get the max element is the remaining tree each time
• downadjust : As mentioned above its to adjust the tree after removing the root node

Now the time complexity of the max heap tree is O(n log n)

See my all posts Shubham Mishra
You can also visit my other posts such as Introduction to Recursion Algorithm and Data Structure and its type

Ok great, we are done with this post,  

Now if you like my way of talk, lets explore more blogs written by me and my inner knowledge,

Get to know answers for common search on Google : A blog for posts which can help you for daily life problems, such as where to get free images, Topic suggestion for the blog.

Computer Science algorithms and other knowledge share : A blog for posts such as best search algorithm, Top interview questions for diffrent technologies, knowledge share for some frameworks or programming languages for the interview or in general terms.

My ideas to solve real world problems : A blog where me shared and presented my ideas to solve a real world problems, this will be interesting for me.

Future of computer science technology discussed : A blog where me discussed about the future of computer science and new technologies which will change our way for looking to solve problems.

Ruby on Rails Web development Blog : As the name suggest, it is the blog for sharing few knowledge about RoR web development framework.

Liked my blogs, wanna to connect:

LinkedIn  |  GitHub  |  HackerEarth  |  ResearchGate  |  Twitter  |  Facebook  |  StackOverflow

Thanks for reading this post, Have a good day :)