# Heap Sort Algorithm in C++

[1986 views]

Heap Sort is one of the best sorting algorithms being in-place and it has no quadratic worst-case running time. Heap sort Algorithm involves building a Heap data structure from the given array and then utilizing the Heap created to sort the array.

Below we have a simple C++ program implementing the Heap sort algorithm.

#### Code:

#include <iostream> #include <ctime> #include <cstdlib> using namespace std; template <class T> class maxHeap{ private: int size=0; T* arr; int capacity; public: maxHeap(int capacity){ arr=new T[capacity]; this->capacity = capacity ; } ~maxHeap(){ delete[] arr; } void add(T& data){ if(size>=capacity){ resize(); } int index = size; size++; arr[index] = data; while(index!=0&&arr[index]>arr[parent(index)]){ swap(index,parent(index)); index=parent(index); } } T extractMax(){ if (size <= 0) { return T(NULL); //return Null object } if (size == 1){ size--; return arr[0]; } // Store the minimum value, and remove it from heap T root = arr[0]; arr[0] = arr[size-1]; size--; MaxHeapify(0);//sort the heap at index 0; return root; } void MaxHeapify(int i){//sort int l = left(i); int r = right(i); int biggest = i; if (l < size && arr[l] > arr[i]) biggest = l; if (r < size && arr[r] > arr[biggest]) biggest = r; if (biggest != i){ swap(i, biggest); MaxHeapify(biggest); } } //secondary functions void resize(){ cout<<"\n(resizing from "<<capacity<<" to "<<capacity*2<<")"<<endl; T* arr2=new T[2*capacity]; for(int i=0;i<capacity;i++){ arr2[i]=arr[i]; } T* temp=arr; arr=arr2; delete[] temp; capacity *=2; } void swap(int index1,int index2){ T temp=arr[index1]; arr[index1]=arr[index2]; arr[index2]=temp; //cout<<"s"; } void print(){ for(int i=0;i<size;i++){ cout<<arr[i]<<"->parent:"<<arr[parent(i)]<<endl; } } int left(int index){return (2*index+1);} int right(int index){return (2*index+2);} int parent(int index){return (index-1)/2;} //getters for readonly T getMin(){return arr[0];} int getSize(){return size;} int getCapacity(){return capacity;} }; class Object{ public: int value; Object(){ // cout<<"x"; } Object(int value){ this->value=value; // cout<<"x"; } Object(const Object& o){ // cout<<"a"; this->value=o.value; } ~Object(){ // cout<<"*" ; }//overloading the < operator for heap sorting bool operator> (const Object& o2){ if(this->value>o2.value)return true; return false; } }; int main() { maxHeap <Object> h(10); srand(time(0)); Object o; cout<<"Populating the heap with random values.\n\n"; for(int i=0;i<10;i++){ o=Object(rand()%100); cout<<o.value<<", "; h.add(o); } //going over capacity, no problem:resizing for(int i=0;i<10;i++){ o=Object(rand()%100); cout<<o.value<<", "; h.add(o); } cout<<endl; cout<<"\nExtracting\n\n"; for(int i=0;i<20;i++){ cout<<(h.extractMax()).value; //h.print(); cout<<","; } return 0; }