Heapsort

http://install4install.com

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

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.

Screen Shot 2014-05-21 at 4.44.07 PM

Fig 1 : Array

 

Array is converted to heap in Fig 2

Screen Shot 2014-05-21 at 4.46.16 PM

Fig 2 : Heap

 

The further steps are illustrated through following figures

Screen Shot 2014-05-21 at 5.47.08 PM

Step 1

Screen Shot 2014-05-21 at 5.49.53 PM

Step 2

Screen Shot 2014-05-21 at 5.51.09 PM

Step 3

Screen Shot 2014-05-21 at 5.58.18 PM

Step 4

Screen Shot 2014-05-22 at 10.22.04 AM

Step 5

Screen Shot 2014-05-22 at 10.25.05 AM

Step 6

 

Screen Shot 2014-05-22 at 10.27.29 AM

Step 7

 

Screen Shot 2014-05-22 at 10.47.37 AM

Step 8

Screen Shot 2014-05-22 at 10.49.30 AM

Step 9

Screen Shot 2014-05-22 at 10.50.36 AM

Step 10

Screen Shot 2014-05-22 at 10.51.45 AM

Step 11

Screen Shot 2014-05-22 at 10.53.55 AM

Step 12

Screen Shot 2014-05-22 at 11.01.39 AM

Step 13

Screen Shot 2014-05-22 at 11.03.13 AM

Step 14

Screen Shot 2014-05-22 at 11.04.04 AM

Step 15

Screen Shot 2014-05-22 at 11.08.46 AM

Step 16

Screen Shot 2014-05-22 at 11.09.40 AM

Step 17

Screen Shot 2014-05-22 at 11.10.35 AM

Step 18

Screen Shot 2014-05-22 at 11.13.24 AM

Step 19

Screen Shot 2014-05-22 at 11.14.41 AM

Step 20

 

Screen Shot 2014-05-22 at 2.48.53 PM

Step 21



Short URL: http://tinyit.cc/020f01
Author: Cusp2207 on May 22, 2014
Category: Computer Science, Data Structures
Tags:

Leave a Reply

Last articles