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.


Heap Sort Algorithm implementation in C++

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; }
        

Struggling to Understand Algorithm and Flowchart? Try our Notes



Want to Test Your Knowledge on Algorithm and Flowchart?



Comments



Recommended Deals End in



Search
Online Games
Play 2048 Game Online and Relax.
Play 2048 Game Online

Search Tags

    C++ Program for Heap Sort Algorithm

    Heap Sort Pseudocode in C++

    Simple C++ code for Heap Sort