# Heap Sort

- Heap Sort Algorithm
- Heap Sort Example
- Heap Sort Algorithm Implementation
- Heap Sort Algorithm Complexity

Heap sort is a comparison-based sorting algorithm. It gets its name from the heap data structure used in the algorithm. Heap is a binary tree based special data structure. It has the following two properties:

- It is a complete binary tree with all levels filled except the last one. The last one may be partially filled, but all the nodes are as far left as possible.
- All the parent nodes are smaller/larger than their two children nodes. If they are smaller, heap is called min-heap, and if larger, then the heap is called max-heap. For a given index
`i`

, the parent is given by`(i-1)/2`

, the left child is given by`(2*i+1)`

and the right child is given by`(2*i+2)`

.

Heap sort works in a manner quite similar to selection sort. It selects the maximum element from the array using max-heap and puts it in its position at the back of the array. It makes use of a procedure called `heapify()`

to build the heap.

## Heap Sort Algorithm

Let us assume that we have an unsorted array `A[]`

containing `n`

elements.

`HeapSort()`

##### Build a max heap with elements present inside array

`A`

.##### For every element starting from the last element in

`A`

do the following.##### The root element

`A[0]`

will contain the maximum element, swap it with this element.##### Reduce the heap size by one and

`Heapify()`

the max heap with the last element removed.

`Heapify()`

##### Initialize

`parent`

index with the index of the current element.##### Compute

`leftChild`

as`2*i+1`

and`rightChild`

as`2*i+2`

.##### If the element at the

`leftChild`

is greater than the value at`parent`

index set`parent`

index to`leftChild`

.##### If the element at the

`rightChild`

is greater than the value at`parent`

index set`parent`

index to`rightChild`

.##### If the value of the

`parent`

index has changed in the last two steps, then swap parent with the current element and recursively`heapify`

the`parent`

index subtree. Otherwise, the heap property is already satisfied.

## Heap Sort Example

Suppose we have the array: `(5, 3, 4, 2, 1, 6)`

. We will sort it using the heap sort algorithm.

After building the heap, we get the array as: `(6 3 5 2 1 4)`

.

- First Iteration:

`Swap(A[5],A[0])` |
`4 3 5 2 1 6` |

`Heapify()` |
`5 3 4 2 1 6` |

- Second Iteration:

`Swap(A[4],A[0])` |
`1 3 4 2 5 6` |

`Heapify()` |
`4 3 1 2 5 6` |

- Third Iteration:

`Swap(A[3],A[0])` |
`2 3 1 4 5 6` |

`Heapify()` |
`3 2 1 4 5 6` |

- Fourth Iteration:

`Swap(A[2],A[0])` |
`1 2 3 4 5 6` |

`Heapify()` |
`2 1 3 4 5 6` |

- Fifth Iteration:

`Swap(A[1],A[0])` |
`1 2 3 4 5 6` |

`Heapify()` |
`1 2 3 4 5 6` |

- Sixth Iteration:

`Swap(A[0],A[0])` |
`1 2 3 4 5 6` |

`Heapify()` |
`1 2 3 4 5 6` |

We get the sorted array as : `(1,2,3,4,5,6)`

## Heap Sort Algorithm Implementation

```
#include<bits/stdc++.h>
using namespace std;
void heapify(int arr[], int n, int i) {
int parent = i;
int leftChild = 2 * i + 1;
int rightChild = 2 * i + 2;
if (leftChild < n && arr[leftChild] > arr[parent])
parent = leftChild;
if (rightChild < n && arr[rightChild] > arr[parent])
parent = rightChild;
if (parent != i) {
swap(arr[i], arr[parent]);
heapify(arr, n, parent);
}
}
void heapSort(int arr[], int n) {
for (int i = n / 2 - 1; i >= 0; i--)
heapify(arr, n, i);
for (int i = n - 1; i >= 0; i--) {
swap(arr[0], arr[i]);
heapify(arr, i, 0);
}
}
int main() {
int n = 6;
int arr[6] = {5, 3, 4, 2, 1, 6};
cout << "Input array: ";
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
cout << "\n";
heapSort(arr, n); // Sort elements in ascending order
cout << "Output array: ";
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
cout << "\n";
}
```

## Heap Sort Algorithm Complexity

### Time Complexity

- Average Case

The height of a complete binary tree with `n`

elements is at max `logn`

. So, the `heapify()`

function can have a maximum of `logn`

comparisons when an element moves from root to leaf. The build heap function is called for `n/2`

elements making the total time complexity for the first stage `n/2*logn`

or `T(n)`

= `nlogn`

.

`HeapSort()`

takes `logn`

worst time for each element, and `n`

elements are making its time complexity also `nlogn`

. Both the time complexity for building heap and heap sort is added and gives us the resultant complexity as `nlogn`

. Hence, the total time complexity is of the order of [Big Theta]: `O(nlogn)`

.

- Worst Case

The worst-case time complexity is [Big O]: `O(nlogn)`

.

- Best Case

The best-case time complexity is [Big Omega]: `O(nlogn)`

. It is the same as the worst-case time complexity.

### Space Complexity

Space Complexity for heap sort algorithm is `O(1)`

because no extra memory other than temporary variables is required.