Heap Sort

  1. Heap Property: Parent is always greater than child
  2. child for parent i are 2i+1 & 2i+2 (zero based starting index).
  3. height of tree is log(n) where n is number of elements.
  4. heap: is a B-Tree with heap property.

Operations:

Inserting element to a Heap: Add the element to the last available position and keep swapping with parent till you find its position.

Heapify a tree A at inex i means make the tree at index i into heap:

Compare A[i] with large of the 2 children and swap if necessary. this MAY break the heap property of the child, so repeat the process with the swap child. O(logn)

Building a Heap: start at n/2 and down to 1 run Heapify at every node. Runs in linear time.

Heap Sort: exchange the last element with max element and decrease the length of the array and repeat the whole process.

 

 

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s