Heap Sort Algorithm


Heap sort algorithm is considered to be the most convenient sorting method that has no worst case time complexity scenario. We can divide the algorithm of heap sort into two parts that are: a heap is created of the unsorted arrays or list, and then an array is constructed in which the largest or smallest elements are inserted from the heap.


What is a Heap?

A heap is a balanced and specialized binary tree data structure in which we compare the root or parent node to the children nodes. And then these nodes are arranged accordingly. This tree based data structure has the following properties:


Shape Property:

The structure of heap should be a complete binary tree that is all levels of the tree should be completely filled. Consider the following figure in which a complete binary tree and an incomplete binary tree are illustrated:


Shape Property


Heap Property:

A heap in data structures is of two types that are min heap and a max heap.

A max heap is the one in which the parent or the root node is greater than or equal to its child nodes. Consider the following figure:

max heap

It can be seen that the max heap has the largest element as the first one. Therefore, when we want to sort the list or array in descending order we use max heap.

A min heap is the one in which the parent or the root node is less than or equal to the child nodes. Consider the following figure:

min heap

It can be seen that the min heap has the smallest element as the first one. Therefore, when we want to sort the list or array in ascending order we use min heap.


How heap sort works:

First of all when an unsorted array or list is received we choose and create the heap data structure either max heap or min heap. When the heap is created the first element of the heap is either largest or it is smallest, it depends on which type of heap we are implementing. Then we put the first element of the heap into our array.

After putting the element in array, a new heap is created of the remaining elements. A new heap is created to again pick the first element and to put it into the array. This process is continued until the list or array is sorted.


Sorting using Heap sort Algorithm:

Consider the following algorithm in which we declared a heapsorting () method or function to call another function named buildingheap () to build a heap. The function buildingheap () further calls another function named buildingheap1 () which builds another heap and the following code is written in C++ programming language:

ALGORITHM:

void heapsorting (int[], int);

void buildingheap (int [], int);

void buildingheap1 (int [], int, int);

void main()

{

  int arr [10], x, length;

  cout << “Enter length of array (max 10)”;

  cin >> length;

  cout << “Enter” << length << “elements of array”;

  for ( x = 0; x < length; x ++)

  {

    cin >> arr [x];

  }

  heapsorting (arr, length);

  getch();

}

void heapsorting (int arr [], int length1)

{

  buildingheap (arr, length1);

  int sizeofheap, x, temp;

  sizeofheap = length1 – 1;

  for ( x = sizeofheap; x > = 0; x –)

  {

    temp = arr [0];

    arr [0] = arr [sizeofheap];

    arr [sizeofheap] = temp;

    sizeofheap –;

    buildingheap1 (arr, 0, sizeofheap);

  }

  for ( x = 0; x < length1; x ++)

  {

    cout << “\t” << arr [x];

  }

}

void buildingheap (int arr [], int length2)

{

  int x, sizeofheap;

  sizeofheap = length2 – 1;

  for ( x = (length2 / 2); x > = 0; x –)

  {

    buildingheap1 (arr, x, sizeofheap);

  }

}

void buildingheap1 (int arr [], int x, int sizeofheap)

{

  int a, b, largest, temp;

  a = 2 * x;

  b = 2 * x + 1;

  if (a < = sizeofheap && arr [a] > arr [x])

  {

    largest = a;

  }

  else

  {

    largest = x;

  }

  if ( b < = sizeofheap && arr [b] > arr [largest])

  {

    largest = b;

  }

  if (largest ! = x)

  {

    temp = arr [x];

    arr [x] = arr [largest];

    arr [largest] = temp;

    buildingheap1 (arr, largest, sizeofheap);

  }

}

In the above algorithm, the three functions are declared (already discussed). The working of algorithm is simple. First in the main function an array of size is declared but is not initialized. We asked the user to enter the size of the array and then asked the user to enter the elements of the array. After this the heapsorting () method is called and the array and its size are passed.

Then heap is created in which the elements of array entered by user are inserted, then the first element of the heap either largest or smallest (depends upon max heap or min heap) is put into array. Again a new heap is created in which remaining elements of array are inserted and the first element of this heap is put into array as the second element. This process continues until the list is sorted.


Complexity Analysis of Heap Sort:

The following are the cases for time complexity of heap sorting:

Worst case Time complexity:

The worst case time complexity is o (n log n)

Best case Time Complexity:

The best case time complexity is o (n log n)

Average Time Complexity:

The average case time complexity is o (n log n)

Space Complexity:

The space complexity is o (n)

The algorithm of heap sorting requires a constant space for sorting a list of elements and hence it is not stable. The algorithm of heap sort is fast and is widely used for sorting lists of elements.