Heap Sort Sorting Algorithm using Min Heap (with full C++ Program)

A Heap is a special Tree-based data structure in which the tree is a complete binary tree. One of the application of a Heap data structure is Heap Sort Sorting algorithm.

Heapsort Sorting Algorithm –

Heap sort is a comparison based sorting technique based on Binary Heap data structure. It is similar to selection sort where we first find the minimum element and place the minimum element at the beginning. We repeat the same process for the remaining elements. In this video we will implement Heapsort Sorting algorithm using C++ Programming Language. Please make sure you first watch Heap Data structure videos for the best understanding.

Min Heap Implementation as Array (Full C++ Program) –

#include<iostream>
#include<math.h>

using namespace std;

class MinHeap {
  public:
    int * harr; // pointer to array of elements in heap
  int capacity; // maximum possible size of min heap
  int heap_size; // Current number of elements in min heap

  MinHeap(int cap) {
    heap_size = cap;
    capacity = cap;
    harr = new int[cap];
  }

  void printArray() {
    for (int i = 0; i < heap_size; i++)
      cout << harr[i] << " ";
    cout << endl;
  }

  int parent(int i) {
    return (i - 1) / 2;
  }

  int left(int i) {
    return (2 * i + 1);
  }

  int right(int i) {
    return (2 * i + 2);
  }
  int getMin() {
    return harr[0];
  }
  void MinHeapify(int i) {
    int l = left(i);
    int r = right(i);
    int smallest = i;
    if (l < heap_size && harr[l] < harr[i])
      smallest = l;
    if (r < heap_size && harr[r] < harr[smallest])
      smallest = r;
    if (smallest != i) {
      swap(harr[i], harr[smallest]);
      MinHeapify(smallest);
    }
  }
  // Method to remove minimum element (or root) from min heap
  int extractMin() {
    if (heap_size <= 0)
      return INT_MAX;
    if (heap_size == 1) {
      heap_size--;
      return harr[0];
    }

    // Store the minimum value, and remove it from heap
    int root = harr[0];
    harr[0] = harr[heap_size - 1];
    heap_size--;
    MinHeapify(0);
    //printArray();
    //cout <<"--"<<harr[0]<<"--";
    return root;
  }

  void getUnsortedArray() {
    cout << "Enter " << capacity << " no of elements to sort using HEAPSORT" << endl;
    for (int i = 0; i < capacity; i++)
      cin >> harr[i];
  }

  void heapSort() {
    int temp[capacity];
    for (int j = 0; j < capacity; j++) {
      //cout<<extractMin()<<" ";
      temp[j] = extractMin();
      cout << temp[j] << " ";
    }
  }

};

int main() {
  int s;
  cout << "Enter Size of Min Heap" << endl;
  cin >> s; // 5
  MinHeap obj(s);
  obj.getUnsortedArray(); // 7 4 3 9 8

  cout << "Unsorted Array :" << endl;
  obj.printArray();

  for (int i = s / 2 - 1; i >= 0; i--) {
    obj.MinHeapify(i);
  }

  //cout << "Heapified Array :"<<endl;
  //obj.printArray();

  cout << "Heap Sorted Array :" << endl;
  obj.heapSort();

}

YouTube video tutorial –