/////////// ********HEAPIFY ALGO**********////////////

// no of leaf nodes = [(n/2+1)th index to (n)th index] 
// n = is equal to the number of index  
//CONCLUSION -> we need to check only from 0 to n/2 because lower than it will be the binary tree as well beacuse of leaf node property 

// heapify function = the function which convert the tree into the heap by interchanging it ....(in this process we will not process the leaf nodes )

#include <iostream>
using namespace std;
 
class heap
{
    public:
    int arr[100];
    int size;
    
    heap()
    {
        arr[0] = -1;
        size = 0;
    }
    
    void insert(int val){
        
        size = size + 1 ;
        int index = size;
        arr[index] = val ;
        while(index > 1){
            int parent = index/2;
            
            if(arr[parent] < arr[index]){
                swap(arr[parent],arr[index]);
                index = parent;
            }
            else{
                return;
            }
        }
    }
    
    void print(){
        for(int i = 1 ; i<=size; i++){
            cout << arr[i] << " ";
        }cout<< endl;
    }
 
    void deletefromHeap()
    {
        if(size == 0){
            cout << "nothing to delete "<< endl;
            return;
        }
        
        // Step 1: Replace root with last element
        arr[1] = arr[size];
        size--;
        
        // Step 2: Take root to its correct position
        int i = 1;
        while(i <= size) // Fix: changed condition to `<= size` to avoid out of bounds
        {
            int leftIndex = 2 * i;
            int rightIndex = 2 * i + 1;
            int largest = i;
        
            // Check if left child exists and is greater
            if(leftIndex <= size && arr[largest] < arr[leftIndex])
            {
                largest = leftIndex;
            }
 
            // Check if right child exists and is greater
            if(rightIndex <= size && arr[largest] < arr[rightIndex])
            {
                largest = rightIndex;
            }
 
            // If largest is still the parent node, break the loop
            if(largest == i) {
                break;
            }
 
            // Swap with the largest child and continue down the heap
            swap(arr[i], arr[largest]);
            i = largest;
        }
    }
};
void heapify(int arr[], int n , int i ){
    int largest = i ;
    int left = 2*i;
    int right = 2*i + 1;
    
    if(left < n && arr[largest] < arr[left]){
        largest = left;
    }
    if(right < n && arr[largest] < arr[right]){
        largest = right;
    }
    if(largest != 1){
        swap(arr[largest],arr[i]);
        heapify(arr, n , largest);
    }
    
}
 
int main()
{
    heap h;
    h.insert(6);
    h.insert(54);
    h.insert(57);
    h.insert(59);
    h.insert(58);
    h.print();
    
    // Delete the root of the heap
    h.deletefromHeap();
    cout << "After deleting root: ";
    h.print();
    
    int arr[6] = {-1 , 54, 53 ,55, 52, 50 };
    int n = 5;
    for(int i = n/2 ; i>0 ; i--){
        heapify(arr , n , i);
    }
    cout << "PRINTING THE ARRAY IN NOW" << endl;
    for(int i = 1; i<n ;i++){
        cout << arr[i]<< endl;
    }
    cout << endl;
    
    return 0;
}