###
**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 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 :-

Heap Sort Is Implemented using Two Mechanisms :-

1. Max Heap

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.

* 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.

* 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

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

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' .**

**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**

Very Nice Explanation

ReplyDeleteGreat article! We are linking to this great article on our website.

ReplyDeleteKeep up the great writing.

Here is my weblog :: Arthur Falcone