Heap Sort

What is a heap?

Heap data structure is an array that can be viewed as a complete binary tree. Which means each node of a tree corresponds to a element in array. Remember complete binary tree?  Complete binary tree is a type of binary tree in which all levels are completely filled except last level which is filled from left to right.

Consider array [4,2,8,3,6,5,1] So first element of array forms a root of a tree.

If we consider array index staring from 1 instead of 0. We can consider how we decide left , right children and parent node of a tree. i is index of array.

Parent : i / 2

Left child:  2 * i

Right child: (2 * i) + 1

If we consider element at index 1 is parent its children will be left child (2*1=2) element at index 2 (2) and right child will be ((2*1)+1 = 3) (8).

If you want to find parent of 6 then you don’t need o picture a tree, using formula one can know that. 6’s index is 5. 5/2=2 so element at index 2 , which 2 is going to be 6’s parent.

If you consider his example, you can see a binary tree can have parent nodes till n/2, if ‘n’ is total number of elements. As each parent will have at the max 2 children, (n/2) + 1 to n  will be leaf nodes.

Heap data structure is of 2 types, Max heap and Min heap.

Max heap:  Value of parent node is always greater than value of its children.

Min heap:  Value of parent node is always minimum than value of its children.

So how heap sort uses min heap or max heap property of heap data structure to sort elements?

Logic:

1. Build a max heap (or min heap depending on the order in which need o sort elements).

2. Place root key in back in array and replace root with leftmost leaf node. Form max heap again and repeat this step again.

Example:

Consider input array as: [4,2,,8,3,6,5]

Implementations:

Explanation:

1. In each call we are going to do heap by calling heapify function and then  swap first element of array(which is root of a tree)  with last element of array ( which is leaf node of tree).  Now after swapping new root may violate a max heap property, but children are max heaps.

2.  In Heapsort call , for loop is from [length-1 to 1] because we will decrease heap size by 1 in each call.

3. In Heapify function call, for loop is from [length/2 to 1] because we know that in array all elements from [length/2+1 to length-1] going to be leaf nodes.

Analysis:

Each call to Heapify function costs O(lg n) time, and HeapSort makes O(n) such calls. So running time for HeapSort is O(n lg n).

Heap sort is  in place and stable sorting algorithm.

Merge Sort

If you are given 4 red sticks of different heights placed from lower to higher height order and 4 green sticks of different heights placed from lower to higher height order. Task is to arrange red and green sticks together from lower to higher height..

A basic way to do this is to pick smallest by comparing smaller sticks of red and green  and place it. Next pick 2nd  highest stick. Continue this till all sticks are placed in correct order. In Merge sort this basic technique of merging to sorted array is used.

Logic:

Merge sort uses a concept of ‘divide and conquer‘ to sort elements.

a.  Divide given elements in half, continue dividing elements unless there is only one element present to sort. As one element is always a sorted element, return and start next step.

b. Merge two elements together in a sorted order. continue merging two sorted sub arrays till all input elements are in sorted order.

Example:

Consider input elements as 4,2,8,1,6,3

Dividing action is performed by calling MergeSort function recursively, in each call mid of  array is calculated and two subarrays are formed like input[start to mid] and input[mid+1 to end] and sorting and merging two subarrays is performed by calling Merge function recursively.

Implementation:

Analysis:

Calculating mid of array takes  constant time regardless of size of the array . So time complexity of this operation is O(1).

When we combine two sorted array , each element is checked so time complexity for this operation is O(n)

In each step array is divided in half and sort two subarrays of size n/2. So the total time complexity of  sorting n elements can be expressed as following :

T(n) = T(n/2) + T(n/2) + O(n)    :: T(n)=2T(n/2) + O(n)

By using Master theorem, Time complexity is O(nlog n)

Merge sort uses an extra space to hold two halves so his sort is not a in place sort and space complexity is O(n).