Array C Programing

Question: Write a short note on the Heap Sort.

Ans: Heap Sort

Heap sort is a method of sorting of elements of the array. Each element is stored in the array in a binary tree representation.

Suppose H is a binary tree is called heap or a max heap, if each node N is greater than or equal to the value of each of children of N. Heapsort may be regarded on a two stage method.

Tree representing the elements is converted into a heap. A heap is defined to be a complete binary tree with the property that the value of each node is at least as large as the value of its children node.

i.e. root always has the max. key.

The output sequence is generated in decreasing order by successively deleting the root and again adjust the tree into a heap.

Complexity of Heap sort is O(nlgn).

 

Example:
In the diagram below, an unsorted Arr array with 6 elements is initially created and then max-heap is built.

 

 

The elements in the arr will be after building max-heap:

 

Step 1: 8 is swapped with 5.
Step 2: 8 is disconnected from heap as 8 is in correct position now and.
Step 3: Max-heap is created and 7 is swapped with 3.
Step 4: 7 is disconnected from heap.
Step 5: Max heap is created and 5 is swapped with 1.
Step 6: 5 is disconnected from heap.
Step 7: Max heap is created and 4 is swapped with 3.
Step 8: 4 is disconnected from heap.
Step 9: Max heap is created and 3 is swapped with 1.
Step 10: 3 is disconnected.

 

 

 

 

 

 

 

 

 

 

 

After all the steps, we will get a sorted array.