FOR FREE CONTENT

Heap Sort using recursion

Back to Programming

Description

Heapsort is a comparison based sorting technique which is depending on the data structure of the binary heap. A complete binary tree in the data structure is a binary tree in which every level is completely filled except the last level. The heap binary tree can be of two types- max heap and min-heap. When the parent node is greater than the left and right child then the tree is known as max heap and when the parent node is lesser than the left and right child then the tree is known as min-heap. It is an in-place sorting algorithm as it does not require any extra storage space to sort the data. The heapsort algorithm is divided into two parts. In the first part, the heap tree is built and in the second step the array is sorted by removing the largest element from the array repeatedly and inserting it at its sorted position and after that, the heap tree is created again. In the array representation of heap tree, if the parent node is at index i then its left child will be at index 2*i, and the right child will be at index 2*i + 1.

 

Procedure of Heapsort:

1. Build the given tree as Max-heap where every root element should larger compare two its Childs.

2. Remove the root element and place it to end of the array i.e. end of the tree as a vacant place.

3. Now, run Max heapify to rebuild the new tree as a Max heap.

4. Same way process will be continued until the end of the tree and all elements are sorted.  

 

Procedure with an example:

Suppose there is an array of 5 elements as following:

 

 

The array has to be sorted in ascending order and we are following the max heap tree to sort the elements. We are considering the array to be started from index 0. So the left child will be at the index 2*i + 1 and the right child will be at the index 2*i + 2.

 

 

First, the heap tree will be created following the max heap data structure. So 3 will be compared to 2 and 4 (the two children of 3) and as 4 is greater than 3, they will be swapped. Now the array will be:

 

 

 

Again -9 will be compared to 4 and 12, in this case both are greater than -9 but as 12 is greater in between two children then -9 will be swapped with 12 and the array will be:

 

 

Now, the max heap is built.

 

The 2nd part is now to eliminate the root (largest element of the array) and will be put at the last node of the tree (last index in array) and also insert the last element as the root.

 

Step 1:

 

 

 

Now we are not considering 12 (removed element) in the tree.   

 

Now, again the max heap will be built from index to n-1 in a previous way. First 4 is compared with its left child 2, as 2 is lesser than 4 so there will be no change. Now 3, the root node will be compared with its left and right child 4 and -9 respectively, as 4 is greater than the root node 3 then it will be swapped. 

 

 

Now again the maximum element will be eliminated again as the following:

 

Step 2:

 

 

 

Now we are not considering element 4 (removed element) in the tree.     

 

Again the max heap will be built using max heapify procedure:

 

 

Now again the root (maximum element) will be eliminated again like the following:

 

Step 3:

 

 

Now the same way we are not considering element 3 (removed element) in the tree.     

 

Again the max heap will be built using max heapify procedure:

 

 

Now again the root (maximum element) will be eliminated again like the following:

 

Step 4:

 

 

The array is sorted now:

 

 

Algorithm

INPUT:   An unsorted array a[6,2,4,1,…………….,n]

OUTPUT:   An sorted array a[1,2,3,4,5,…………..,n] (in ascending order)

 

PROCESS:

Step 1: [read the number of elements and array elements]

Read n

For i = 0 to n repeat

Read arr[i]

 

Step 2: [‘MAX_HEAPIFY’ function to arrange the elements of the array]

MAX_HEAPIFY(A, i)

            {           l = 2i

                        r = 2i + 1

                        if(l <= A.heap_size and A[l] > A[i])

                                    largest = l;

                        else

                                    largest = i;

if(r <= A.heap_size and A[r] > A[largest])

                                    largest = r;

                        If( largest  i)

                                    exchange A[i] with A[largest]

                                    MAX_HEAPIFY(A, largest)

            }

 

Step 3: [‘HeapSort’ function to sort the array]

HeapSort(A)

{           Build_MAX_Heap(A)

            for(i = A.length down to i)

            exchange A[1] with A[i]

            A.heap_size = A.heap_size – 1

            MAX_HEAPIFY(A, 1)

}

 

Step 4: [display the sorted array]

For i =0 to n repeat

Print A[i]

[End of ‘for’ loop]

Code

CHARACTERISTICS:

1. It is a comparison based sorting technique.

 

2. It is an in-place sorting mechanism that does not require any extra storage space for sorting.

 

3. It can be thought of as an improved selection sort.

 

4. The heap tree can be represented using an array.

 

TIME COMPLEXITY:

The time taken to build the heap for n elements is O(n).

Each of the n - 1 calls to arrange the element using the MAX_HEAPIFY function takes O(logn) time.

 

HeapSort(A)

{           Build_MAX_Heap(A)     --------------- O(n)

            for(i = A.length down to i)  ----------- n-1

            exchange A[1] with A[i]

            A.heap_size = A.heap_size – 1

            MAX_HEAPIFY(A, 1)    --------------------  n-1 * O(logn)

}

 

Therefore the time complexity of heap sort is:

The complexity is the same for all three cases i.e. Best case, the average case, and the worst case.

 

SPACE COMPLEXITY:

The space complexity is  O(1) as no extra space is needed to sort the elements of the array.

 

ADVANTAGES:

1. It is an efficient sorting algorithm.

 

2. It is a simple algorithm that can be implemented very easily.

 

3. It performs equally for best case, average case and worst case i.e. Its performance is consistent.

 

4. It does not require any extra storage space to sort the elements.

 

DISADVANTAGES:

1. It is an unstable sorting algorithm.

 

2. Storing the data in heap is slower than storing data in a stack.

 

APPLICATION:

1. It is used in interval scheduling.

 

2. Heapsort is applied in the priority queue.