Heapsort in Data Structure

There is a long queue at the billing counter of a mall. Some people have put all of their groceries in the cart and some have only 8-10 items. You have only a packet of chips and bread. Suppose you are in the 10th position in the queue, you could have to wait a long time for your billing. But what if the billing counter bills the persons who will require the least amount of time first. You will be billed first followed by some people with a small number of items and people with the largest number of items will be billed last.

This is how a heap sort works. It is the fastest way to find the smallest or largest element in a dataset.

Heapsort in Data Structure

Heap sort works by creating a min-heap or max-heap out of the elements provided in a dataset. Ordering of the dataset in which root element represents the minimum or maximum element is represented by min heap and max heap. Heapsort is similar to selection sort, where the smallest element is found and is put at the first position.

Binary heap

A binary tree is complete if all the levels are completely filled except possibly the last level and the last level has all keys as left as possible. This is known as a complete binary tree.

A binary heap is a complete binary tree with the following properties :

• In a min-heap, the root node must be minimum among all keys present in the binary heap. This is true for all nodes in the binary tree.
• In a max heap, the root node must be maximum among all keys present in the binary heap. This is true for all nodes in the binary tree.

A binary heap is a complete binary tree. Therefore, it can be easily represented as an array since arrays are space-efficient. If the parent node is stored at index I, the left child is at 2 * I + 1, and the right child is at 2 * I + 2.

Procedure for Heapsort

Procedure for sorting an array in ascending order:

1. Create a max heap from an input dataset

2. Replace the largest element at the root with the last item of the heap. Reduce the size of the heap by 1.

3. Heapify the root of the tree.

4. Repeat steps 2 and 3 while the size of the heap is greater than 1

Heapsort Algorithm

HEAP_SORT(Array, N)

Step 1: [Building heap H]

for i=0 to N-1

INSERTHEAP(Aeray, N, Array[i])
[END OF for]

Step 2: Repeatedly Delete the root element
while N > 0
DeleteHeap(Array,N,value)
N = N+1

[END OF while]
Step 3: stop

Working of heapsort

Let us try to sort the following array using the heap sort technique

1: create a tree with the elements of the array

2: Convert the tree to max heap

3: swap the root with the last element of the heap.

4: Heapify and repeat.

5:

6: Heapify the above heap.

7:

8:

9:

10:

11:

Heap is not a stable sorting algorithm.

Implementation of Heapsort in C

#include <stdio.h>

  void swap(int *x, int *y) 
  {
    int temp = *x;
    *x = *y;
    *y = temp;
  }
  
  void heapify(int arr[], int size, int i) 
  {
    int largest = i;
    int low = 2 * i + 1;
    int high = 2 * i + 2;
  
    if (low < size && arr[low] > arr[largest])
      largest = low;
  
    if (high < size && arr[high] > arr[largest])
      largest = high;
  
    if (largest != i) 
    {
      swap(&arr[i], &arr[largest]);
      heapify(arr, size, largest);
    }
  }
  
  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 array[] = {54, 12, 9, 35, 26, 40,100,73,81,66};
    int size = sizeof(array) / sizeof(array[0]);
  
    heapSort(array, size);
  
    printf("Sorted array: \n");
    for (int i = 0; i < size; ++i)
      printf("%d ", array[i]);
  }

Heapsort Implementation in C++

#include <iostream>
using namespace std;

  void swap(int *x, int *y) 
  {
    int temp = *x;
    *x = *y;
    *y = temp;
  }
  
  void heapify(int arr[], int size, int i) 
  {
    int largest = i;
    int low = 2 * i + 1;
    int high = 2 * i + 2;
  
    if (low < size && arr[low] > arr[largest])
      largest = low;
  
    if (high < size && arr[high] > arr[largest])
      largest = high;
  
    if (largest != i) 
    {
      swap(&arr[i], &arr[largest]);
      heapify(arr, size, largest);
    }
  }
  
  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 array[] = {54, 12, 9, 35, 26, 40,100,73,81,66};
    int size = sizeof(array) / sizeof(array[0]);
  
    heapSort(array, size);
  
    cout << "Sorted array:";
    for (int i = 0; i < size; ++i)
      cout << " " << array[i];
  }

Heapsort Implementation in Java

public class HeapSort 
{
    public void sort(int array[]) 
    {
      int size = array.length;
      
      for (int i = size / 2 - 1; i >= 0; i--) 
      {
        heapify(array, size, i);
      }
      
      for (int i = size - 1; i >= 0; i--) 
      {
        int temp = array[0];
        array[0] = array[i];
        array[i] = temp;
  
        heapify(array, i, 0);
      }
    }
  
    void heapify(int arr[], int n, int i) 
    {
      int largest = i;
      int low = 2 * i + 1;
      int high = 2 * i + 2;
  
      if (low < n && arr[low] > arr[largest])
        largest = low;
  
      if (high < n && arr[high] > arr[largest])
        largest = high;
        
      if (largest != i) 
      {
        int swap = arr[i];
        arr[i] = arr[largest];
        arr[largest] = swap;
  
        heapify(arr, n, largest);
      }
    }
  
  
    public static void main(String args[])
    {
      int arr[] = { 54, 12, 9, 35, 26, 40,100,73,81,66 };
  
      HeapSort hs = new HeapSort();
      hs.sort(arr);
  
      System.out.println("Sorted array:");
      int n = arr.length;
      for (int i = 0; i < n; ++i)
        System.out.print(arr[i] + " ");
    }
  }

Implementation of Heapsort in Python

def heapify(arr, n, i):
    
      largest = i
      low = 2 * i + 1
      high = 2 * i + 2
  
      if low < n and arr[i] < arr[low]:
          largest = low
  
      if high < n and arr[largest] < arr[high]:
          largest = high
  
      if largest != i:
          arr[i], arr[largest] = arr[largest], arr[i]
          heapify(arr, n, largest)
  
  
def heapSort(arr):
      size = len(arr)
  
      for i in range(size//2, -1, -1):
          heapify(arr, size, i)
  
      for i in range(size-1, 0, -1):
          arr[i], arr[0] = arr[0], arr[i]
          heapify(arr, i, 0)
  
  
arr = [54, 12, 9, 35, 26, 40,100,73,81,66]
heapSort(arr)
n = len(arr)
print("Sorted array:")
for i in range(n):
    print("%d " % arr[i], end='')

Complexity of Heapsort

Best case complexity: when the pivot element is the middle element or near to the middle element.

Worst-case complexity: when pivot element is either largest or smallest number.

Average case complexity: when the condition of best and worst-case, both don’t occur.

Applications of heapsort

Although heapsort has limited applications since quicksort and mergesort techniques are much better, it has some eminent applications.

1. Heapsort is used in the Linux kernel because of its O(1) space complexity and O(n log n) time complexity.

2. Heap sort returns the largest or smallest element in the dataset in the fastest time. It is used in places that need minimum or maximum elements without requiring the rest of the dataset to be sorted. For example, priority queues.

Conclusion

The heap sort technique is based on the binary tree data structure. We will study binary trees in detail in future articles. Max heap and min heap are created for sorting in ascending or descending order respectively. There are some other sorting techniques also that we have not covered since these are the few often used techniques. With this article, we end our topic for sorting techniques.