Facebook

Heapsort

The Maxheap sorts the elements in increasing order whereas Minheap sorts the element in decreasing order.To sort the heap three steps have to be followed

  • Heapify -The process picks the largest child key and compare it to the parent key. If parent key is larger than key then heapify quits, otherwise it swaps the parent key with the largest child key. So that the parent  now becomes larger than its children.
  • Build Heap - Use the procedure 'Heapify' in a bottom-up fashion to convert an array  into a heap. The process starts from last nodes and not the leaves.
  • Heap Sort - Sorting is done by removing the max element and storing in array .The storage starts from last position and goes till first index of array.

Time Analysis

  • Build Heap Algorithm will run in O(n) time
  • There are n-1 calls to Heapify each call requires O(log n)time
  • Heap sort program combine Build Heap program and Heapify, therefore it has the running time of  O(n log n) time
  • Total time complexity: O(n log n)

Example

Given an array in Fig 1 .We need to convert it to Maxheap and sort it.

Fig 1:An Array

 

Array is converted to heap in Fig 2

Fg 2 : A Heap

 

The further steps are illustrated through following figures:

Fig 3 : Step 1
Fig 4 : Step 2
Fig 5 : Step 3
Fig 5 : Step 4
Fig 6 :Step 5
Fig 7 : Step 6
Fig 8 : Step 7

 

Fig 9 : Step 8

 

Fig 10 :Step 9
Fig 11 : Step 10
Fig 12 : Step 11

 

Fig 13 : Step 12
Fig 14 : Step 13
Fig 15 :Step 14
Fig 16 : Step 15
Fig 17 : Step 16
Fig 18 : Step 17
Fig 19 : Step 18
Fig 20 : Step 19
Fig 21 : Step 20
Fig 22 : Step 21
Rate this post

Comments

So empty here ... leave a comment!

Leave a Reply

Your email address will not be published. Required fields are marked *

Sidebar