Heap concepts and Heap sort

A heap is special tree-based data structure, with the tree being a Complete binary tree. (All levels are completely filled). It is a special, balanced binary-tree data structure where root node is compared with its children, and arranged according to the type of heap.

Binary Tree

A binary tree is a tree data structure which has at most 2 children (i.e. 0, 1, 2 only), referred to as left and right children.

Complete binary tree.

A Binary Tree is complete Binary Tree if all levels are completely filled except possibly the last level and the last level has all keys as left as possible .

Heaps are of 2 types :-

1.Max Heap : Max heap is that heap which has all its parent nodes value greater than its children nodes.It should be recursively true for all sub-trees in that Binary Tree.

2.Min Heap : Min Heap is that heap which has all its parent nodes value lesser than its children nodes.It should be recursively true for all sub-trees in that Binary Tree.

Heapify !!!!

Heapify is the process of converting a binary tree into a Heap data structure, i.e. to convert it into either a max heap or min heap.

Algorithm

1.Start
2.Take as input array,size of array, i (index)
3.Assign values 
    3.1 largest = i
    3.2 left = 2 * i + 1  (left child)
    3.3 right = 2 * i + 2 (right child)
4. if  left< n and array[l] >arr[largest] is true
    4.1 Assign largest = left

5.if  right< n and array[r] >arr[largest] is true
    5.1 Assign largest = right
6. if largest != i
     6.1 swap array[i] and array[largest]
     6.2 call heapify function again with parameters array, n ,largest
7.End

Explanation

The heapify function coverts a binary tree to max/min heap.We create a MAX heap using the above algorithm.

We take as parameters array,its size and index. We initialize a variable with index. The left and right children are assigned their values in terms of index. There may occur 3 conditions:-

1. left < sizeof(array) and array[left] > array[largest], i.e. the left child’s value is greater than its parent ,we assign largest = left child
2. right < sizeof(array) and array[right] > array[largest] , ie the right child’s value is greater than its parent ,we assign largest = right child
3. if largest != index ,this means our tree is still not heap ,we swap array[i] with array[largest] and call heapify function again passing array,sizeof(array),largest as parameters.

Heap sort

Heap sort is sorting technique which uses the concepts of heap to sort elements. It’s very similar to selection sort where we place the largest element at the end.

Algorithm

1.Start
2.Make max heap 
3.Swap the root with the minimum element of the heap
4.Call heapify function 
5.Repeat the steps 2 to 4 till elements are sorted
6.End

Lets understand through an example:-

Explanation

In heap sort , we first create max-heap.Now the root element(array[0]) is the largest element of the present heap.We swap this root element with the least(last) value of the heap array .Now we call heapify function and exclude the last element as its already at its correct position ,then we decrease the size of heap by 1. We repeat the above steps till all the elements are in their correct positions.

Time and Space Comlexity

Worst-case-complexity	O( N log N)
Best-case-complexity	O( N log N)
Average-case-complexity	O( N log N)
Worst-case-space-complexity	O(1)

Explanation

In this sort,we swap the root element and the last element and heapify the root element.Hence,for each element,this will take O(log N ) and since we repeat it N times ,the time complexity of heap sort is O(N log N).

Hence in simple words, Building a heap takes O(N) and each call to heapify function makes O(log N) calls. Thus complexity is O(N) * O(log N) = O( N log N) .

Advantages

Its main advantage is its efficiency : Execution time complexity O( N log N) and space complexity O(1).

Disadvantage

It is slower than merge and quick sort.

---

How about an awesome summary on sorting in the next post? Stay tuned!

For any doubts or ambiguities, mail us at everythinggeeky.101@gmail.com, or comment below! 

Don’t forget to Like, Comment and Share with your friends.

Stay Tuned for Everything Geeky.

See you next week!

Cheers!

Team Bitxorbytes

Follow us on instagram:  @bitxorbytes

http://clipart-library.com/baby-sheep-cliparts.html