What is a heap?

**Heap** data structure is an array that can be viewed as a complete binary tree. Which means each node of a tree corresponds to a element in array. Remember complete binary tree? Complete binary tree is a type of binary tree in which all levels are completely filled except last level which is filled from left to right.

Consider array [4,2,8,3,6,5,1] So first element of array forms a root of a tree.

If we consider array index staring from 1 instead of 0. We can consider how we decide left , right children and parent node of a tree. i is index of array.

**Parent : i / 2**

**Left child: 2 * i**

**Right child: (2 * i) + 1**

If we consider element at index 1 is parent its children will be left child (2*1=2) element at index 2 (2) and right child will be ((2*1)+1 = 3) (8).

If you want to find parent of 6 then you don’t need o picture a tree, using formula one can know that. 6’s index is 5. 5/2=2 so element at index 2 , which 2 is going to be 6’s parent.

If you consider his example, you can see a binary tree can have parent nodes till n/2, if ‘n’ is total number of elements. As each parent will have at the max 2 children, (n/2) + 1 to n will be leaf nodes.

Heap data structure is of 2 types, Max heap and Min heap.

**Max heap: **Value of parent node is always greater than value of its children.

**Min heap: **Value of parent node is always minimum than value of its children.

So how heap sort uses min heap or max heap property of heap data structure to sort elements?

**Logic:**

1. Build a max heap (or min heap depending on the order in which need o sort elements).

2. Place root key in back in array and replace root with leftmost leaf node. Form max heap again and repeat this step again.

Example:

Consider input array as: [4,2,,8,3,6,5]

**Implementations:**

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 |
private void HeapSort(int[] input) { int length = input.Length; for (int i = length - 1; i >= 0; i--) { MaxHeapify(input, i); Swap<int>(ref input[0], ref input[i]); } } private void MaxHeapify(int[] input, int length) { for (int i = length / 2; i >=0; i--) { int largestIndex = i; int max = input[i]; int left = (2 * i) + 1; int right = (2 * i) + 2; if (left <= length && input[left] < input[i]) { max = input[left]; largestIndex = left; } if (right <= length && input[right] < max) { max = input[right]; largestIndex = right; } if (largestIndex != i) { Swap<int>(ref input[largestIndex], ref input[i]); } } } public void Swap<T>(ref T a, ref T b) { T temp = a; a = b; b = temp; } |

**Explanation:**

1. In each call we are going to do heap by calling heapify function and then swap first element of array(which is root of a tree) with last element of array ( which is leaf node of tree). Now after swapping new root may violate a max heap property, but children are max heaps.

2. In Heapsort call , for loop is from [length-1 to 1] because we will decrease heap size by 1 in each call.

3. In Heapify function call, for loop is from [length/2 to 1] because we know that in array all elements from [length/2+1 to length-1] going to be leaf nodes.

**Analysis:**

Each call to Heapify function costs O(lg n) time, and HeapSort makes O(n) such calls. So running time for HeapSort is O(n lg n).

Heap sort is in place and stable sorting algorithm.