#include <iostream>
#include <vector>
using namespace std;

//Lecture Based
void InsertA(int* A, int n)
{
    int i=n; // i = 9
    int temp= A[n]; // temp = 50
    while(i>0&&temp>A[i%2 == 0 ? (i/2)-1:i/2])
    {
        // if odd, A[i/2]
        // if even A[i/2+1]
        A[i] = A[i%2 == 0 ? (i/2)-1:i/2];
        // first, A[9] = A[5] = 10;
        i = i%2 == 0 ? (i/2)-1:i/2; // 4;
    }
    A[i] = temp;
    // result 50,35,45,30,15,12,6,5,20,10
}
void Insert(vector<int>& vec, int key)
{
    // insert key at the end
    auto i = vec.size();
    vec.emplace_back(key);

    //Rearrange elements: indices are not DRY
    while(i>0 && key>vec[i%2 == 0 ? (i/2)-1:i/2])
    {
        vec[i]= vec[i%2 == 0 ? (i/2)-1:i/2];
        i = i%2 == 0 ? (i/2)-1:i/2;
    }
    vec[i] = key;
}
template <class T>
void Print(T& vec,int n)
{
    cout<<"Max Heap:[ " <<flush;
    for(int i=0; i<n; i++)
    {
        cout<<vec[i]<<flush;
        if(i<n-1)
        {
            cout<<" , " <<flush;
        }
    }
    cout<<" ] " <<endl;
}
int main()
{
    int a[] = {45, 35, 15, 30, 10, 12, 6, 5, 20, 50};
    int size_ = sizeof(a)/sizeof(a[0]);
    InsertA(a, 9);
    cout<< "size = " << size_ << endl;
    // InsertA(a,9);
    Print(a,size_);
    cout<<endl;

    // STL Based
    vector<int> v = {45, 35, 15, 30, 10, 12, 6, 5, 20}; // heap memeory
    Print(v,size_);
    v.reserve(15);  // Reserve space for 15 elements

    Insert(v,50);
    Print(v,size_);
    return 0;
}

#include <iostream>
#include <vector>

using namespace std;

template<class T>
void Print(T& vec, int n, char c)
{
    cout<< c << ":[" <<flush;
    for(int i = 0; i<n; i++)
    {
        cout << vec[i]<< flush;
        if(i<n-1)
        {
            cout <<"," <<flush;
        }
    }
    cout << "] " <<endl;
}

void Insert(vector<int>& vec, int key)
{
    //insert Key at the end, if there is nothing, size is zero
    auto i = vec.size();
    vec.emplace_back(key);

    // Rearrange elements: O(log n)
    while(i>0 && key>vec[i%2==0?(i/2)-1:i/2])
    {
        vec[i] = vec[i%2==0?(i/2)-1:i/2];
        i = i%2==0?(i/2)-1:i/2;
    }
    vec[i] = key;
}
void CreateHeap(vector<int>& vec, int A[], int n)
{
    //O(n logn)
    for(int i=0; i<n; i++)
    {
        Insert(vec,A[i]);
    }
}
void insertinplace(int A[],int n)
{
    int i = n;
    int temp = A[n];
    while(i>0 && temp>A[i%2==0?(i/2)-1:i/2])
    {
        A[i]=A[i%2==0?(i/2)-1:i/2];
        i = i%2==0?(i/2)-1:i/2;
    }
    A[n] = temp;
}
void createHeap(int A[], int n)
{
    for(int i=0; i<n; i++)
    {
        insertinplace(A,i);
    }
}


int main()
{
    cout << "Create Heap" << endl;
    int b[] = {10, 20, 30, 25, 5, 40, 35};
    Print(b, sizeof(b)/sizeof(b[0]), 'b');

    vector<int> v;
    CreateHeap(v,b,sizeof(b)/sizeof(b[0]));
    Print(v, sizeof(b)/sizeof(b[0]), 'v');

    cout << "Inplace Insert" << endl;
    createHeap(b, sizeof(b)/sizeof(b[0]));
    Print(b, sizeof(b)/sizeof(b[0]), 'b');

    return 0;
}

#include <stdio.h>

void Insert(int A[], int n)
{
    int i = n;
    int temp = A[i];
    while(i>0 && temp>A[i/2])
    {
        A[i]=A[i/2];
        i=i/2;
    }
    A[i] = temp;
}

void Delete(int A[], int n)
{
    int i,j,x,temp, val;
    val = A[1];
    x = A[n];
    A[1] = A[n];
    A[n] = val;
    i=1;
    j=i*2;
    while(j<=n-1)
    {
        if(j<n-1 && A[j+1] > A[j])
        {
            j=j+1;
        }
        if(A[i]<A[j])
        {
            temp = A[i];
            A[i] = A[j];
            A[j] = temp;;
            i = j;
            j = 2*j;
        }
        else
            break;
    }
}

int main()
{
    int H[] = {0,14,15,5,20,30,8,40};
    int i;
    for(i=2;i<=7;i++)
    {
        Insert(H,i);
    }
    for(i=1;i<=7;i++)
    {
        printf("%d ", H[i]);
    }
    printf("\n");
    for(i=7;i>1;i--)
    {
        Delete(H,i);
    }
    for(i=1;i<=7;i++)
    {
        printf("%d ", H[i]);
    }
    printf("\n"); // result : 0 5 8 14 15 20 30
    return 0;
}

#include <iostream>

using namespace std;

template<class T>
void Print(T& vec, int n, string c)
{
    cout<< c << " : [" <<flush;
    for(int i =0; i<n;i++)
    {
        cout<< vec[i] << flush;
        if(i<n-1)
        {
            cout<<" ,"<<flush;
        }
    }
    cout<<"]"<<endl;
}
void Swap(int A[], int i, int j)
{
    int temp = A[i];
    A[i] = A[j];
    A[j] = temp;
}
void Heapify(int A[], int n)
{
    // # of leaf elements: (n+1)/2, index of last leaf elements parent = (n/2)-1
    for(int i = (n/2) -1 ; i>=0; i-- )
    {
        int j = 2*i +1; // left child for current i, at first n ;

        while(j<n-1)
        {
            //Compare left and right children of current i ;
            if(A[j]<A[j+1])
            {
                j = j+1;
            }

            // Compare Parent and largest child
            if(A[i]<A[j])
            {
                Swap(A,i,j);
                i = j;
                j= 2*i + 1;
            }
            else
                break;
        }

    }
}
int main()
{
    int A[] = {5, 10, 30, 20, 35, 40, 15};
    Print(A, sizeof(A)/sizeof(A[0]),"A");

    Heapify(A,sizeof(A)/sizeof(A[0]));
    cout<<endl;
    Print(A, sizeof(A)/sizeof(A[0]),"A");
    return 0;
}