# 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**quit**s, 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**hea**p. 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.

Array is converted to heap in **Fig 2**

The further steps are illustrated through following figures:

## Comments

So empty here ... leave a comment!