## Heap sort

Heap sort is achieved with the help of selection type of sorting logic along with heap attributes of the array. Heap data structure is a binary tree with some special structural orientation often known as complete binary tree. Logic of heap data structure and heap attribute of an array is used in heap sorting. To understandheap we need to understand binary tree and some related terms. Let us understandthese one by one.

## Binary Tree

Binary Tree is the simplest form of tree data structure where each node can have max of two children, known as left and right. The node of a Binary Tree is formed with two pointers to point child nodes named as left and right.

## Full Binary Tree

A full Binary tree is a tree in which every node in the level of (height - 1) should have two children and the nodes at the higest level has no child. A full Binary tree has maximum number of nodes at its hight level. Addition of a single node in the tree will cause the height to reise by one.

## Complete binary tree

A complete binary tree is similar to a full binary tree, but with two major differences

• Complete binary tree should be completely filled to the height level h-1 but may not be completely filled at highest level (h).
• New nodes must me added starting from left side and thus all the leaf elements must lean towards the left.
• The last leaf element might not have a right sibling i.e. a complete binary tree doesn't have to be a full binary tree.

Here are some example binary tree nodes. Some qualifies the property of complete binary tree.

Here are some example 2nd level binary trees. Some qualifies the property of complete binary tree.

## Heap Data Structure

Heap is a special binary tree based data structure. A binary tree is said to follow a heap data structure if it is a complete binary tree. There are two types of heap structure. Max heap and min heap.

## Max heap/Descending heap

Max heap is a heap structure where parent element is always larger than child elements. This ordering rule is maintained in the entire tree. Thus all the parent elements are larger than children elements in any level of the tree and the root contains the largest value.

## Min heap/Assending heap

Min heap is a heap structure where parent element is lower than child elements. Thus root of the min heap contains the lowest value and the further we go to the depth, values are larger.

## Binary Heap and array elements mapping

There is a relation between binary tree and array. A Binary Heap is a complete Binary Tree and it can be represented as an array. Each element index in array can be mapped to a node in binary tree. In the reverse case also it is true. A tree node node can be mapped to an index in the array. Array indexing starts with 0 and root in binary tree is the starting element. The root can be placed at index zero. Since we populate child elements from left side so first left should be at index 1 and right should be be at index 2. In general if the parent node is stored at index i, the left child can be calculated by (2 * i + 1) and right child by (2 * i + 2).

## Heap Sort Algorithm :

Sorting can be in ascending or descending order. Either Max heap or min heap logic can be taken depending on the need.

1. Build a max/min heap using Heapify() from the input data.
2. At this point, the largest/smallest item is stored at the root of the heap. Replace it with the last item of the heap followed by reducing the size of heap by 1. Finally, heapify the root of tree.
3. Repeat above steps while size of heap is greater than 1.

void heap_sort(int arr[], int n)
{
/* Build heap (rearrange elements) */
for (int i = n / 2 - 1; i >= 0; i--)
heapify(arr, n, i);

/* One by one extract an element from heap */
for (int i=n-1; i>=0; i--)
{
/* Move current root to end */
swap(&arr[0], &arr[i]);

/* call max heapify on the reduced heap */
heapify(arr, i, 0);
}
}

## Heapify /build the heap

Heapify is the core procedure for arranging elements in the heap. Building heap can have two logics -

1. Building Max heap or
2. Building Min heap
In Max heap logic, root is taken as max element. Then it is compared with left and right. If left or right has the larger then the item is swapped with root. After that this Heapify procedure is recursively called to the sub tree.

Logic for min heap remains similar but it selects and swaps for the min element.

Heapify procedure can be applied to a node only if its children nodes are heapified. So the heapification must be performed in the bottom up order. Heap sort algorithm calls Heapify() from N -1 index till index 0.

void max_heapify(int arr[], int n, int i)
{
int largest = i; /* largest as root */
int l = (* i) + 1; /* left */
int r = (* i) + 2; /* right */

/* If left child is larger than root */
if (< n && arr[l] > arr[largest])
largest = l;

/* If right child is larger than largest so far*/
if (< n && arr[r] > arr[largest])
largest = r;

/* If largest is not root */
if (largest != i)
{
swap(&arr[i], &arr[largest]);

/* Recursively heapify the sub-tree */
max_heapify(arr, n, largest);
}
}

## Heapsort example source

/* Example C program implements Heap Sort algo */
#include <stdio.h>

/* An utility function to print array of size n */
void print_array(int arr[], int n)
{
if (<= 0)
return;

for (int i = 0; i < n; ++i)
{
printf("%d ", arr[i]);
}
printf("\n");
}

/* Swaps two array elements */
void swap (int *a, int *b)
{
int tmp;
tmp = *a;
*= *b;
*= tmp;
}
/******************************************/
/* To heapify(min) subtree root @ index i */
/* Arguments - */
/* ARR[] - Input array */
/* N - Size of the array */
/* I - Index of the heap's root */
/******************************************/
void min_heapify(int arr[], int n, int i)
{
int smallest = i;    /* smallest as root */
int l = (* i) + 1; /* left */
int r = (* i) + 2; /* right */

/* If left child is smaller than root */
if (< n && arr[l] < arr[smallest])
smallest = l;

/* If right child is smaller than smallest so far*/
if (< n && arr[r] < arr[smallest])
smallest = r;

/* If smallest is not root */
if (smallest != i)
{
swap(&arr[i], &arr[smallest]);

/* Recursively heapify the sub-tree */
min_heapify(arr, n, smallest);
}
}

/******************************************/
/* To heapify(max) subtree root @ index i */
/* Arguments - */
/* ARR[] - Input array */
/* N - Size of the array */
/* I - Index of the heap's root */
/******************************************/
void max_heapify(int arr[], int n, int i)
{
int largest = i; /* largest as root */
int l = (* i) + 1; /* left */
int r = (* i) + 2; /* right */

/* If left child is larger than root */
if (< n && arr[l] > arr[largest])
largest = l;

/* If right child is larger than largest so far*/
if (< n && arr[r] > arr[largest])
largest = r;

/* If largest is not root */
if (largest != i)
{
swap(&arr[i], &arr[largest]);

/* Recursively heapify the sub-tree */
max_heapify(arr, n, largest);
}
}

void (* heapify) (int arr[], int n, int i);

/******************************************/
/* Heap sort algorithm example */
/* Arguments : */
/* ARR[] - Input array */
/* N - Size of the array */
/******************************************/
void heap_sort(int arr[], int n)
{
/* Build heap (rearrange elements) */
for (int i = n / 2 - 1; i >= 0; i--)
{
printf ("Build heap @index #%d\n", i);
heapify(arr, n, i);
print_array(arr, n);
}

/* One by one extract an element from heap */
for (int i=n-1; i>=0; i--)
{
/* Move current root to end */
printf ("Move current root %d to end\n", arr[0]);
swap(&arr[0], &arr[i]);

print_array(arr, i);
if (i)
printf ("Build heap rearranging elements\n");

/* call max heapify on the reduced heap */
heapify(arr, i, 0);
print_array(arr, i);
}
}

#define SORT_ASCENING 1 /* 1 or 0*/

int main()
{
int arr[] = {25, 67, 56, 32, 12, 96, 82, 44};
int n = sizeof(arr)/sizeof(arr[0]);

#if SORT_ASCENING
printf ("Sorting in ascending order using max heap \n");
heapify = max_heapify ;
#else
printf ("Sorting in descending order using min heap \n");
heapify = min_heapify ;
#endif

printf ("Original array is \n");
print_array(arr, n);
heap_sort(arr, n);

printf ("Sorted array is \n");
print_array(arr, n);
}

## Heap sort output

```Sorting in ascending order using max heap
Original array is
25 67 56 32 12 96 82 44
Build heap @index #3
25 67 56 44 12 96 82 32
Build heap @index #2
25 67 96 44 12 56 82 32
Build heap @index #1
25 67 96 44 12 56 82 32
Build heap @index #0
96 67 82 44 12 56 25 32
Move current root 96 to end
32 67 82 44 12 56 25
Build heap rearranging elements
82 67 56 44 12 32 25
Move current root 82 to end
25 67 56 44 12 32
Build heap rearranging elements
67 44 56 25 12 32
Move current root 67 to end
32 44 56 25 12
Build heap rearranging elements
56 44 32 25 12
Move current root 56 to end
12 44 32 25
Build heap rearranging elements
44 25 32 12
Move current root 44 to end
12 25 32
Build heap rearranging elements
32 25 12
Move current root 32 to end
12 25
Build heap rearranging elements
25 12
Move current root 25 to end
12
Build heap rearranging elements
12
Move current root 12 to end
Sorted array is
12 25 32 44 56 67 82 96
```

## Heap sort steps -diagrams

```Sorting in ascending order using max heap
Original array is
25 67 56 32 12 96 82 44
Build heap @index #3
25 67 56 44 12 96 82 32
```

```25 67 56 44 12 96 82 32
Build heap @index #2
25 67 96 44 12 56 82 32
```

```25 67 96 44 12 56 82 32
Build heap @index #1
25 67 96 44 12 56 82 32
```

```25 67 96 44 12 56 82 32
Build heap @index #0
96 67 82 44 12 56 25 32
```

```Move current root 96 to end
32 67 82 44 12 56 25
Build heap rearranging elements
82 67 56 44 12 32 25
```

```Move current root 82 to end
25 67 56 44 12 32
Build heap rearranging elements
67 44 56 25 12 32
```

```Move current root 67 to end
32 44 56 25 12
Build heap rearranging elements
56 44 32 25 12
```

```Move current root 56 to end
12 44 32 25
Build heap rearranging elements
44 25 32 12
```

```Move current root 44 to end
12 25 32
Build heap rearranging elements
32 25 12
```

```Move current root 32 to end
12 25
Build heap rearranging elements
25 12
```

```Move current root 25 to end
12
Build heap rearranging elements
12
```

```Move current root 12 to end
Sorted array is
12 25 32 44 56 67 82 96
```

## Heap sort descending order

```Sorting in descending order using min heap
Original array is
25 67 56 32 12 96 82 44
Build heap @index #3
25 67 56 32 12 96 82 44
Build heap @index #2
25 67 56 32 12 96 82 44
Build heap @index #1
25 12 56 32 67 96 82 44
Build heap @index #0
12 25 56 32 67 96 82 44
Move current root 12 to end
44 25 56 32 67 96 82
Build heap rearranging elements
25 32 56 44 67 96 82
Move current root 25 to end
82 32 56 44 67 96
Build heap rearranging elements
32 44 56 82 67 96
Move current root 32 to end
96 44 56 82 67
Build heap rearranging elements
44 67 56 82 96
Move current root 44 to end
96 67 56 82
Build heap rearranging elements
56 67 96 82
Move current root 56 to end
82 67 96
Build heap rearranging elements
67 82 96
Move current root 67 to end
96 82
Build heap rearranging elements
82 96
Move current root 82 to end
96
Build heap rearranging elements
96
Move current root 96 to end
Sorted array is
96 82 67 56 44 32 25 12

```