Saturday 24 August 2013

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





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 






Share this

2 Responses to "Explain HeapSort With Example "

  1. Very Nice Explanation

    ReplyDelete
  2. Great article! We are linking to this great article on our website.
    Keep up the great writing.

    Here is my weblog :: Arthur Falcone

    ReplyDelete