geeksprogrammings: Explain HeapSort With Example

Heap Sort is a Sorting Mechanism Developed by J. W. J. Williams

We have looked at various Sorting Algorithms but the faster sorting algorithms in the average and best case time and Algorithm that did not require any space over and above what was needed to store the input is a Heap Sort Algorithm

Heap sort is Performed by implementation of Heap Data Structure. A Heap is a complete Binary Tree . Heap sort is very fast and Heap data Structure are well known for Arranging the elements in Particular Ascending or Descending Order.

Heap Sort Is Implemented using Two Mechanisms :-

1. Max Heap
2. Min Heap

* Max Heap :- In Max Heap the Parent Node is always greater than its Children Node. The Node or Elements on Left and Right Hand Side of Parent node Must be smaller than the Element Value in Parent Node.

* Min Heap :- In Min Heap the Parent Node is always Smaller than its Children Node. The Node or Elements on Left and Right Hand Side of Parent node Must be greater than the Element Value in Parent Node.

A Heap is A Data Structure . A Heap is a Complete Binary Tree in Which Elements on Right and left side of Parent Node must be Smaller or Higher than the Parent Node . A binary tree is a heap if all nodes in it have the heap property

Quicksort is generally faster, but Heapsort is better in time-critical applications

Heap Sort is performed in 2 Steps :-

1. First the given Elements are Represented in form of Heap
2. Then These elements are Sorted using Heap Sort

A heap is a complete binary tree, where all the parents are greater than their children (max heap). If all the children are greater than their parents it is considered to call the heap a min-heap

EXAMPLE of A HEAP :-

Heap Sort Algorithm

Example of Node Does Or Does Not Have Heap Property

Heap Sort Algorithm

---------------------------------------------------------------------------

EXAMPLE TO DEMONSTRATE USE OF HEAP SORT

1. Given an array of 6 elements: 15, 19, 10, 7, 17, 16, sort it in ascending order using heap sort.

STEPS :-

1. First the given Elements are Represented in form of Heap
2. Then These elements should be organized in Max Heap
3. Then Sort it .

A. Building Heap Tree

( i ) Arrange all given elements as Arranged in Fig 1

Heap Sort Algorithm

Fig1

( i i ) Start From Rightmost Node As in Fig1 we can see rightmost element '10' is Parent Node of '16' But in Max Heap in Parent is larger than children . so Replace '16' with '10'. As shown in Fig2

Heap Sort Algorithm

Fig 2

( iii ). Here In Fig 2 '15' is Parent of '19' and Parent is smaller than children so Replace '19' with '15' as shown below

Heap Sort Algorithm

( iv ). Again Parent Node '15' is smaller than children Node '17' so Replace '15' with '17'. as shown below .

Heap Sort Algorithm

( v ) Now First Step is complete Max Head process Done Now Sorting Process Start

B. Sorting

( i ) Starting From Rightmost Element That is last element in all elements of Heap Replace the Max element means First Node Element with last or Rightmost Element of Heap .

Replace '10' with '19'

Last = last -1 . So last is decreased Now '19' is placed at its correct position Now we will Process rest of elements not include '19'

Heap Sort Algorithm

Fig 3

( ii ) Now As we can See in Fig 3 that Parent Element '10' is smaller than it children Element '17' so Replace '17' with '10'

Heap Sort Algorithm

Fig 4

( iii ) Now we can see in Fig 4 that Parent element '10' is smaller than its Children Element '15' so Replace '10' with '15'

Heap Sort Algorithm

Fig 5

( iv ) So Now the Maximum value Element '17' with Last Element . Now last Element is not 19 as in STep 1 last = last -1 so Last is '10' . So interchange '17' with '10'

Heap Sort Algorithm

Fig 6

( v ) Now in Fig 6 we can see Parent Node '10' is Less than Children Node '16' so Interchange '10' and '16'.

Heap Sort Algorithm

Fig 7

( VI ) Now in Fig 7 We can see Max Element except 16 is at First Node . so its time to place 16 to its original location similar to 17 and 19 in step 1 and step 4 respectively.

last = last -1

Heap Sort Algorithm

Fig 8

( VII ) Now we can see Parent Node '7' is smaller than Child Node '15' so Interchange '15' with '7' .

Heap Sort Algorithm

Fig 9

( VIII ) Now in Fig 9 we can see Max element '15' is at First Node or Max Heap Location so now it time to place '15' at its original location. So Replace '15' with location value Last

last = last -1

Heap Sort Algorithm

Fig 10

( IX ) So Now Heap contains two elements that are not organized at their original loacation 10 and 7

( X ) Now we can see First Node Contains the Highest Element of Heap '10' so Finally Put '10' at its original location. Interchange '10' with '7'

Heap Sort Algorithm

Fig 11

( XI ) Now Heap Shown in Fig 11 is contain all Elements in Ascending Sorted Order