Max Heap

#include<iostream>
#include<algorithm>

class MaxHeap{
    int* arr;
    int maxSize;
    int heapSize;
public:
    explicit MaxHeap(int size) {
        heapSize = 0;
        maxSize = size;
        arr = new int[size];
    }
    void MaxHeapify(int i);
    int removeMax();
    void increaseKey(int i, int newVal);
    void deleteKey(int i);
    void insertKey(int x);
    void displayHeap();
    void HeapSort();
    static int parent(int i){
        return (i - 1) / 2;
    }
    static int LeftChild(int i){
        return (2 * i + 1);
    }
    static int RightChild(int i){
        return (2 * i + 2);
    }
    int getMax(){
        return arr[0];
    }
    int curSize(){
        return heapSize;
    }
};

// Increases value of the key at index 'i' to new_val
void MaxHeap::increaseKey(int i, int newVal) {
    arr[i] = newVal;
    while(i != 0 && arr[parent(i)] < arr[i]){
        std::swap(arr[i], arr[parent(i)]);
        i = parent(i);
    }
}

void MaxHeap::deleteKey(int i) {
    //Setting key to max value and then removing it
    increaseKey(i, INT_MAX);
    removeMax();
}

void MaxHeap::insertKey(int x) {
    //Allocating more space
    if(heapSize == maxSize){
        int* newArr = new int[2 * maxSize];
        for(int i = 0; i < maxSize; i++){
            newArr[i] = arr[i];
        }
        delete[] arr;
        arr = newArr;
        maxSize *= 2;
    }

    heapSize++;
    //Initially inserted at the end
    int i = heapSize - 1;
    arr[i] = x;
    //Making sure max heap property satisfied
    while(i != 0 && arr[parent(i)] < arr[i]){
        std::swap(arr[i], arr[parent(i)]);
        i = parent(i);
    }
}

//Remove the root node which is the max element
int MaxHeap::removeMax() {
    if(heapSize <= 0){
        return INT_MIN;
    }
    if(heapSize == 1){
        heapSize--;
        return arr[0];
    }

    //storing the max element
    int root = arr[0];

    //last element is made the root
    arr[0] = arr[heapSize - 1];
    heapSize--;

    //Restore the property of the heap
    MaxHeapify(0);
    return root;
}

void MaxHeap::MaxHeapify(int i) {
    int l = LeftChild(i);
    int r = RightChild(i);
    //Set current element as largest and swap accordingly
    int largest = i;
    if(l < heapSize && arr[l] > arr[i]){
        largest = l;
    }
    if(r < heapSize && arr[r] > arr[largest]){
        largest = r;
    }
    if(largest != i){
        std::swap(arr[i], arr[largest]);
        MaxHeapify(largest);
    }
}

void MaxHeap::displayHeap() {
    for(auto i = 0; i < heapSize; i++){
        std::cout << arr[i] << " ";
    }
    std::cout << "\n";
}

void MaxHeap::HeapSort() {
    int* sortedArray = new int[heapSize];
    int* tempArray = new int[maxSize];
    int tempsize = heapSize;
    // Copy the original array to tempArray
    std::copy(arr, arr + tempsize, tempArray);
    // Perform heap sort and store the sorted elements in sortedArray
    for (auto i = tempsize - 1; i >= 0; i--) {
        sortedArray[i] = removeMax();
    }
    for(auto i = 0; i < tempsize; i++){
        std::cout << sortedArray[i] << " ";
    }
    std::cout << "\n";
    delete[] arr;
    heapSize = tempsize;
    arr = tempArray;
    // Copy elements back to arr
//    std::copy(tempArray, tempArray + tempsize, arr);
}

void prompts(){
    std::cout << "1: Display the array \n";
    std::cout << "2: Insert a key \n";
    std::cout << "3: Size of the heap\n";
    std::cout << "4: Maximum element \n";
    std::cout << "5: Delete a key \n";
    std::cout << "6: Perform Heap Sort \n";
    std::cout << "0: EXIT \n";
    std::cout << "Enter your choice: \n";
}

int inputValue(){
    int value;
    std::cout << "Enter a value: \n";
    std::cin >> value;
    return value;
}

int main(){
    MaxHeap maxheap(10);
    int choice = 10;
    while(choice != 0){
        prompts();
        std::cin >> choice;
        switch (choice) {
            case 0:
                std::cout << "Exited Successfully! \n";
                break;
            case 1:
                std::cout << "The heap array: \n";
                maxheap.displayHeap();
                break;
            case 2:
                maxheap.insertKey(inputValue());
                break;
            case 3:
                std::cout << "The current size of the heap is: " << maxheap.curSize();
                std::cout << "\n";
                break;
            case 4:
                std::cout << "The max(root) element is: " << maxheap.getMax();
                std::cout << "\n";
                break;
            case 5:
                maxheap.deleteKey(inputValue());
                break;
            case 6:
                std::cout << "The sorted array: \n";
                maxheap.HeapSort();
                break;
            default:
                std::cout << "Not a valid choice! \n";
                break;
        }
    }
    return 0;
}