heaps.cpp

#include<iostream>
using namespace std;
class heap{
    public: 
    int arr[100];
    int size;
    heap(){
        arr[0] = -1;
        size = 0;
    }

    void insert(int val){
        size += 1;
        int index = size;
        arr[index] = val;

        while(index>1){
            int parent = index/2;
            if(arr[index] > arr[parent]){
                swap(arr[index],arr[parent]);
                index = parent;
            }
            else{
                return;
            }
        }

    }

    void deleteFromHeap(){
        if(size == 0){
            return ;
        }
        arr[1] = arr[size];
        int i = 1;
        size--;
        cout << "Deleting from heap..." << endl;
        while(i < size){
            int leftIndex = 2*i;
            int rightIndex = 2*i + 1;
            if(leftIndex<size && arr[leftIndex] > arr[i]){
                swap(arr[leftIndex],arr[i]);
                i = leftIndex;
            }
            else if(rightIndex<size && arr[rightIndex] > arr[i]){
                swap(arr[rightIndex],arr[i]);
                i = rightIndex;
            }
            else{
                return;
            }
        }
    }

    void print(){
        for(int i = 1; i<=size; i++){
            cout << arr[i] << " ";
        }
        cout << endl;
    }
};

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 != i){
        swap(arr[largest],arr[i]);
        heapify(arr,n,largest);
    }
}

void heapSort(int arr[],int n){
    while(n > 1){
        swap(arr[1],arr[n]);
        n--;
        heapify(arr,n,1);
    }
}
int main(){
    // heap h;
    // h.insert(23);
    // h.insert(40);
    // h.insert(55);
    // h.insert(70);
    // h.insert(30);
    // h.insert(60);
    // h.print();
    // h.deleteFromHeap();
    // 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 now: " << endl;
    for(int i = 1; i<=n;i++){
        cout << arr[i] <<" ";
    }
    cout << endl;

    cout << "sorted array " << endl;
    heapSort(arr,n);
    for(int i = 1; i<=n;i++){
        cout << arr[i] <<" ";
    }
    cout << endl;
}