#ifndef HEAP_H
#define HEAP_H

class heap
{
        friend ostream &operator<<( ostream&, const heap & );
       
private:
        Type *array;
        int MaxSize, Nel;
        // Max. size of the heap, no. of elements
        void Adjust(Type a[], int i, int n);
public:
        heap(int MSize):
        heap (const heap &);
        ~heap();
        heap &operator+ (const heap &);
        heap &operator+=(const heap &);
        heap &operator+ (int );
        operator=( const heap &);
        operator[]( int);
        bool Insert(Type item);
        // Insert item.
        bool DelMax(Type& item);
        // Delete the maximum.
};
#endif

#include <iostream>
#include "heap.h"
using namespace std;

heap:: heap(int size)
MaxSize(MSize)
{
        array = new Type[MaxSize+1];
        Nel=0;
};

heap::~heap()
{
        delete []array;
};

heap::heap (const heap &a)
{
        array=new Type [MaxSize+1];
        for (int i=0;i=MaxSize;i++)
                array[i]=a[i];
}
friend ostream &operator<<( ostream &output, const heap &a)
{
        int i;
       
        // output private ptr-based array
        for ( i = 0; i = a.MaxSize; i++ ) {
                output << setw( 12 ) << a.array[ i ];
               
                if ( ( i + 1 ) % 4 == 0 ) // 4 numbers per row of output
                        output << endl;
               
        } // end for
       
        if ( i % 4 != 0 )  // end last line of output
                output << endl;
       
        return output;   // enables cout << x << y;
       
} // end function operator<<

const heap::heap &operator+ (const heap &heap1)
{
        Type *array1;
        int x=sizeof(heap1)/4;
        array1=new[Maxsize+2+x];
        for (int i=0;i=MaxSize;i++)
                array1[i]=array[i];
        for (i=Maxsize;i=x+MaxSize;i++)
                array1[i]=heap1.array[i-MaxSize];
        delete []array1;
};

const heap::heap &operator+=(const heap &right)
{
        Type *array1;
        MaxSize1=MaxSize;
        array=new Type[MaxSize+1];
        for (int i=0;i=MaxSize;i++)
                array1[i]=array[i];
        delete []array;
        MaxSize=MaxSize1+sizeof(right.array)/4;
        Type *array;
        array=new Type[MaxSize+1];
        for (i=0;i=MaxSize1;i++)
                array[i]=array1[i];
        for (i=MaxSize1+1;i=MaxSize;i++)
                array[i]=right.array[i-MaxSize-1];
}

const heap::heap &operator+ (int x)
{
        MaxSize=Maxsize+1;
        array[MaxSize]=x;
}


const heap &heap::operator=( const heap &right )
{
        if ( &right != this )   // check for self-assignment
        {
                // for arrays of different sizes, deallocate original
                // left-side array, then allocate new left-side array
                if ( MaxSize != right.size )
                {
                        delete [] array;         // reclaim space
                        MaxSize = right.MaxSize;     // resize this object
                        array = new int[ MaxSize ]; // create space for array copy
                       
                } // end inner if
               
                for ( int i = 0; i < MaxSize; i++ )
                        array[ i ] = right.array[ i ];  // copy array into object
               
        } // end outer if
        return *this;   // enables x = y = z, for example
       
} // end function operator=

int &heap::operator[]( int subscript )
{
        // check for subscript out of range error


        if ( subscript < 0 || subscript >= MaxSize ) {
                cout << "\nError: Subscript " << subscript
                        << " out of range" << endl;
               
                exit( 1 );  // terminate program; subscript out of range
               
        } // end if
       
        return array[ subscript ]; // reference return
       
} // end function operator[]






bool heap::Insert(Type item)
{   // Inserts item.
        int i = ++Nel;
        if (i==MaxSize)
        {
                cout << "heap size exceeded"
                        << endl;
                return false;
        }
        while ((i>1) && (array[i/2]<item))
        {
                array[i] = array[i/2];
                i /= 2;
        }
        array[i] = item;
        return true;
}


void heap::Adjust(Type a[], int i, int n)
// The complete binary trees with roots 2*i and 2*i+1 are
// combined with node i to form a heap rooted at i. No
// node has an address greater than n or less than 1.
{
        int j = 2*i, item = a[i];
        while (j <= n)
        {
                if ((j<n) && (a[j]<a[j+1]))
                        j++;
                // Compare left and right child
                // and let j be the larger child.
                if (item >= a[j])
                        break;
                // A position for item is found.
                a[j/2] = a[j];
                j *= 2;
        }
        a[j/2] = item;
}

bool heap::DelMax(Type& item)
{
        if (!Nel)
        { cout << "heap is empty"<< endl;
        return false;
        }
        item=array[1];
        array[1]=array[Nel--];
        Adjust(array, 1, Nel);
        return true;
};