What is Heap Sort? explain with an example

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.

Binary tree root and children

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.

Full Binary tree

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.

Complete Binary tree

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

Examples of complate Binary tree

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

Examples of complate 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.

Max heap

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.

Min haep

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 node and array index mapping calculation

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 = (2 * i) + 1; /* left */
  int r = (2 * i) + 2; /* right */
  
  /* If left child is larger than root */ 
  if (l < n && arr[l] > arr[largest]) 
    largest = l; 
  
  /* If right child is larger than largest so far*/ 
  if (r < 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 (n <= 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;
  *a = *b;
  *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 = (2 * i) + 1; /* left */
  int r = (2 * i) + 2; /* right */
  
  /* If left child is smaller than root */
  if (l < n && arr[l] < arr[smallest]) 
    smallest = l; 
  
  /* If right child is smaller than smallest so far*/ 
  if (r < 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 = (2 * i) + 1; /* left */
  int r = (2 * i) + 2; /* right */
  
  /* If left child is larger than root */ 
  if (l < n && arr[l] > arr[largest]) 
    largest = l; 
  
  /* If right child is larger than largest so far*/ 
  if (r < 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

max-heapify-at-index-3.png

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

max-heapify-at-index-2.png

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

max-heapify-at-index-1.png

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

max-heapify-at-index-0-0.png

max-heapify-at-index-0-2.png

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

move1-max-heapify.png

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

move2-max-heapify.png

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

move3-max-heapify.png

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

move4-max-heapify.png

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

move5-max-heapify.png

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

move6-max-heapify.png

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

move7-max-heapify.png

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

move8-max-heapify.png

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

About our authors: Team EQA

You have viewed 1 page out of 252. Your C learning is 0.00% complete. Login to check your learning progress.

‹ # ›

Questions index C Questions C++ Questions Win32 MFC COM/DCOM DLL Questions