FULL Heap code in (C++)

                                                   

                                                     

 


#include <iostream>
#include <stdlib.h>
using namespace std;
int heapSize = 0;

void insertMinHeap(int **arrOld, int value)
{
    heapSize++;
    int *arr = new int[heapSize+1];
    arr[heapSize] = value;
    arr[0] = -999;
    for(int i = 1; i < heapSize; i++)
    {
        arr[i] = *(*arrOld+i);
    }
    delete []arrOld;
    *arrOld = arr;
    int c = heapSize;
    int p = c/2;
    while(p > 0)
    {
        if(arr[p] > arr[c])
        {
            int tmp = arr[p];
            arr[p] = arr[c];
            arr[c] = tmp;
            c = p;
            p = c/2;
        }
        else break;
    }
}

bool isMinHeap(int arr[], int sz)
{
    for(int i = 1; i <= sz/2; i++)
    {
        int p = i;
        int lc = 2*p;
        int rc = (2*p)+1;
        if(lc == sz && arr[p] > arr[lc])
        {
            return false;
        }
        else if(lc < sz)
        {
            if(arr[p] > arr[lc] || arr[p] > arr[rc])
                return false;
        }
    }
    return true;
}

bool isMaxHeap(int arr[], int sz)
{
    for(int i = 1; i <= sz/2; i++)
    {
        int p = i;
        int lc = 2*p;
        int rc = (2*p)+1;
        if(lc == sz && arr[p] < arr[lc])
        {
            return false;
        }
        else if(lc < sz)
        {
            if(arr[p] < arr[lc] || arr[p] < arr[rc])
                return false;
        }
    }
    return true;
}

void minHeapify(int arr[], int sz)
{
    int last_p = sz/2;
    for(int i = last_p; i > 0; i--)
    {
        int p = i;
        int lc = 2*p;
        int rc = (2*p)+1;
        int sc = -1;
        if(lc == sz)
        {
            sc = lc;
        }
        else if(lc < sz)
        {
            sc = arr[lc] > arr[rc]? rc : lc;
        }
        if(sc != -1)
        {
            if(arr[p] > arr[sc])
            {
                int tmp = arr[p];
                arr[p] = arr[sc];
                arr[sc] = tmp;
                int curr_p = sc;
                while(1)
                {
                    int lft = 2*curr_p;
                    int rght = (2*curr_p)+1;
                    if(lft == sz)
                    {
                        if(arr[lft] < arr[curr_p])
                        {
                            int tmp = arr[lft];
                            arr[lft] = arr[curr_p];
                            arr[curr_p] = tmp;
                            curr_p = lft;
                        }
                        else break;
                    }
                    else if(lft < sz)
                    {
                        int swc = arr[lft] > arr[rght]? rght:lft;
                        if(arr[swc] < arr[curr_p])
                        {
                            int tmp = arr[swc];
                            arr[swc] = arr[curr_p];
                            arr[curr_p] = tmp;
                            curr_p = swc;
                        }
                        else break;
                    }
                    else break;
                }
            }
        }
    }
}

void maxHeapify(int arr[], int sz)
{
    int last_p = sz/2;
    for(int i = last_p; i > 0; i--)
    {
        int p = i;
        int lc = 2*p;
        int rc = (2*p)+1;
        int sc = -1;
        if(lc == sz)
        {
            sc = lc;
        }
        else if(lc < sz)
        {
            sc = arr[lc] < arr[rc]? rc : lc;
        }
        if(sc != -1)
        {
            if(arr[p] < arr[sc])
            {
                int tmp = arr[p];
                arr[p] = arr[sc];
                arr[sc] = tmp;
                int curr_p = sc;
                while(1)
                {
                    int lft = 2*curr_p;
                    int rght = (2*curr_p)+1;
                    if(lft == sz)
                    {
                        if(arr[lft] > arr[curr_p])
                        {
                            int tmp = arr[lft];
                            arr[lft] = arr[curr_p];
                            arr[curr_p] = tmp;
                            curr_p = lft;
                        }
                        else break;
                    }
                    else if(lft < sz)
                    {
                        int swc = arr[lft] < arr[rght]? rght:lft;
                        if(arr[swc] > arr[curr_p])
                        {
                            int tmp = arr[swc];
                            arr[swc] = arr[curr_p];
                            arr[curr_p] = tmp;
                            curr_p = swc;
                        }
                        else break;
                    }
                    else break;
                }
            }
        }
    }
}

void deleteMinHeap(int arr[],int sz)
{
    int tmp = arr[sz];
    arr[sz] = arr[1];
    arr[1] = tmp;
    heapSize--;
    minHeapify(arr, heapSize);
}

void deleteMaxHeap(int arr[],int sz)
{
    int tmp = arr[sz];
    arr[sz] = arr[1];
    arr[1] = tmp;
    heapSize--;
    maxHeapify(arr, heapSize);
}

void printHeap(int arr[])
{
    if(heapSize == 0)
    {
        cout << "Empty heap!" << endl;
        return;
    }
    cout << endl;
    for(int i = 1; i <= heapSize; i++)
    {
        cout << arr[i] << " ";
    }
    cout << endl;
}

void descendingHeapSort(int arr[], int sz)
{
    for(int i = 1; i <= sz; i++)
    {
        deleteMinHeap(arr, heapSize);
    }
    heapSize = sz;
}

void ascendingHeapSort(int arr[], int sz)
{
    for(int i = 1; i <= sz; i++)
    {
        deleteMaxHeap(arr, heapSize);
    }
    heapSize = sz;
}

int main()
{
    int *arr = new int[31]{-999,65,76,34,51,11,87,66,44,34,90,8,12,10,15,17,22,11,89,85,99,11,29,55,45,75,99,40,14,11,32};
    heapSize = 30;
    maxHeapify(arr, heapSize);
    ascendingHeapSort(arr, heapSize);
    printHeap(arr);
    maxHeapify(arr, heapSize);
    ascendingHeapSort(arr, heapSize);
    for(int i = 0; i < 10; i++)
        insertMinHeap(&arr, (rand()%100)+i);
    printHeap(arr);
    cout << boolalpha << isMinHeap(arr, heapSize);
}