Create a MaxHeap from a given non-arranged vector and also implement Heap Sort functionality. Time complexity constraints of all the methods are described.

MaxHeap.cpp

#include<bits/stdc++.h>
using namespace std;

class MaxHeap{
	private:
		//Variables
		vector<int> v;
		int size;
	
		//Properties
		
		int left(int i){//Time complexity O(1)
			return 2*i + 1;
		}
		
		int right(int i){//Time complexity O(1)
			return 2*i + 2;
		}
		
		void setSize(int sizeVar){//Time complexity O(1)
			size = sizeVar;
		}
		
		int getSize(){ //Time complexity O(1)
			return size;
		}
		
		int getHeight(){ //Time complexity O(log(n))
			int count=0,temp = getSize();
			while(temp){
				count++;
				temp = temp/2;
			}
			return count;
		}
		
		void maxHeapify(vector<int> vec,int i){ // Time complexity O(h) -> h is height of heap
			if(i >= getSize()){
				return;
			}
			int l,r,largest;
			l = left(i);
			r = right(i);
			largest = i;
			//If left child > parent
			if(l < getSize() && v[l] > v[i])
				largest = l;
			//If right child > largest
			if(r < getSize() && v[r] > v[largest])
				largest = r;
			if(largest != i){
				swap(v[i],v[largest]);
				//maxHeapify(largest);
			}
			maxHeapify(v,l); //Call maxHeapify for left child
			maxHeapify(v,r); //Call maxHeapify for right child
		}
		
	public:
		//Constructor
		MaxHeap(){
		}
		
		//Methods
		
		int getMax(){//Time complexity O(1)
			return v[0];
		}
		
		void buildMaxHeap(vector<int> vec){ //Time complexity O(nlog(h))
			v = vec;
			setSize(v.size());
			for(int i=getSize()/2;i>=0;i--){ //Logic is to call maxHeapify from (size of heap)/2 instead of just top to cover all the possible non-maxHeapified elements
				maxHeapify(v,i);
			}
		}
		
		void sort(){ //Time complexity O(nlog(n)) -> precisely O(nlog(h))
			buildMaxHeap(v);
			for(int i=v.size()-1;i>0;i--){ // n
				swap(v[i],v[0]);//Send largest element to the last position
				setSize(getSize() - 1); //We decrease size of heap by 1 so that when next maxHeap element is to be swapped it is swapped by second last and so on.
				maxHeapify(v,0); // multiplied by log(n) or log(h)
			}
			setSize(v.size()); // Again set size of heap back to original
			for(int i=0;i<getSize();i++){
				cout << v[i] << " ";
			}
			cout << endl;
			buildMaxHeap(v);
		}
		
		void display(){ //Time complexity O(n)
			for(int i=0,k=0;i<getHeight();i++){
		        for(int j=0;j<pow(2,i) && k<getSize();j++,k++){
		        	cout << v[k] << " ";
				}
	        	cout << endl;
    		}
		}
};

int main(){
	vector <int> v;
	for(int i=0;i<15;i++){
		v.push_back(i+1);
	}
	
	MaxHeap heap;
	heap.buildMaxHeap(v);
	heap.display();
	heap.sort();
	heap.display();
	cout << heap.getMax();
	return 0;
}

Example to understand maxHeapify method

Example to understand buildMaxHeap method

Example to understand heapSort


And similar to how it goes for 16, it goes on till we get a sorted array.
PS: Examples are taken from Cormen