Hello friends, this is my next article in the series to explain all the sorting algorithms with C# examples. Before understand heap sort we should be very clear about the heap data structure. In this article I will only explain the heap data structure and its properties.
Heap Data Structure and Its properties
Lets first understand about the heap data structure. Heap is a binary tree which supports below conditions:
Shape property
A leaf node at depth k>0 can exist only if all 2k−1 nodes at depth k−1 exist. Additionally, nodes at a partially filled level must be added “from left to right.” This means that suppose I am at height 2, I will start to add leaf node s at height 2, if all the elements at 22−1 exists i.e all there should be a;ready be 2 elements present.
Take one more example, I should start to add elements to the height 3 if 23−1 elements exists i.e. 4 elements should be present in the previous level.
Heap property
Each node in the tree contains a value greater than or equal to either of its two children, if it has any.
Convert an Array to tree
Lets take an array as an example and see how we can convert it to a tree structure.
{5,2,7,3,6,1,4}
Below is the figure of the above array converted to a tree. We started with 0 index and placed the element at the root. Now add 2 and 7 as two children of the root node.
Now add next elements starting from the left to right. 3,6,1 and 4 are added at the next level.
The figure has the elements with index number from the array.I believe the below figure is understandable.
The digits outside of the circle are the index in the array.
One thing we can conclude from the above figure is that, if we are taking an element from index i in the array. The left child of the element will be at index 2i and right child of the element at index (2i+1).
Using the above formula for children we can convert an array in to an in place heap. It means that we don’t have to create a different data structure to convert an array into heap.
In the below figure, I have numbered the elements starting from 1 to n. 1 being assigned to root node and moving down the tree and numbering from left to right.
And as per the heap property I have added one more element 8 at the bottom.
If I put the above tree in an array. The elements will be placed as shown in the figure below. And I have shown the level to which each element belongs to.
Now all the elements without any child nodes are known as leaf nodes. In the above tree the leaf nodes start from element at index 5. So to find the position from which leaf nodes starts, we can use a simple formula |n/2| + 1.
For example, in the above tree I have eight elements, therefore using the above formula my leaf node start from element at index 5.
Conclusion
In this article I explained you about the heap data structure and its properties which will help you to solve the heap sort algorithm. I will discuss the heap sort algorithm in my next article.