///////////////************* HEAPS ***************/////////////////


//// WHAT IS HEAP ?
// complete binary tree comes with a complete binary tree properies as well as heap order property ...

// what is complete binary tree? 
// every level is full filled (fully filled means every parent node have 2 children and always filled from left side only  )  except the last level  nodes always added on left.. 

//// HEAPS PROPERTY
// MAX HEAP = parent ka child humesha use CHOTA honga 
// MIN HEAP = parent ka child humesha use BADA honga 

// suppose node index is i
// so, its left child will be at (2*i)th index.
// so, its right child will be at ((2*i)+1th) index.
// so, its parent will be at (i/2)


///MAP HEAP INSERTION
//STEP1 - INSERT AT THE END 
//STEP2 - COMAPRE IT WITH ITS PARENT NODE IF IT IST BIGGER THAN IT SHIFT IT TO THE TOP (FORMULA WE WILL USE PARENT = INDEX OF CHILD / 2)

// DELETION IN AN HEAP 
//STEP1 - REPALCE THE ROOT NODE WITH LAST NODE (SWAPPED)
//STEP2 - DELETE THE ROOT NODE NOW 
//STEP3 - COMPARE IT WITH ITS ALL CHILDREN AND REPLACE IT WITH MAX HEAP PROPERTY

///////////*** insertion in max heap ************///////////////
#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;
        }
    }
};

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();
    
    return 0;
}