Need Help in Heap Code in C++

[Pratim]

I am doing the practice in C++ programming language. Since I have recently started with the C++, I am not having that much knowledge in it. And I have got the assignment in which I have to provide a C++ class to implement a MAX heap of integers. I have also been told that I have to use the appropriate constructors for the class. Also the operator[] should be used for accessing the individual elements of the heap as they were stored in a sorted array. Can anyone help me solving my problem.?? Does anyone know the Heap Code in C++??

[Katty]

I think that the code below should help you.

#include <Classes.hpp>
#include <Controls.hpp>
#include <StdCtrls.hpp>
#include <Forms.hpp>

class TForm1 : public TForm
{
public:
    TButton *btnSort;
    TListBox *lbItems;
    TButton *btnAdd;
    TButton *btnClear;
    TButton *btnExit;
    void __fastcall btnSortClick(TObject *Sender);
    void __fastcall btnClearClick(TObject *Sender);
    void __fastcall btnAddClick(TObject *Sender);
    void __fastcall btnExitClick(TObject *Sender);
private:
    int a[255];     //255 elements max
    int heapsize;
    int elements;
public:
    __fastcall TForm1(TComponent* Owner);
    void heapsort();
    void buildheap();
    void heapify(int i);
};
extern PACKAGE TForm1 *Form1;

[Zecho]

According to me the coding given by 'Katty' is not complete. After creating the form you will have to put the coding of Heap Sort into it. Use this coding after using the coding given by the Katty.

#include <vcl.h>
#pragma hdrstop
#pragma package(smart_init)
#pragma resource "*.dfm"
TForm1 *Form1;
__fastcall TForm1::TForm1(TComponent* Owner)
    : TForm(Owner)
{
}
void TForm1::heapsort()
{
    int t;
    int k;

    buildheap();

    for (k=elements;k>=1;k--)
    {
        t=a[k];
        a[k]=a[0];
        a[0]=t;
        heapsize--;
        heapify(0);
    }
}

void TForm1::buildheap()
{
    int j;
    heapsize=elements+1;
    for (j=((elements+1) / 2) - 1;j>=0;j--) heapify(j);
}

void TForm1::heapify(int i)
{
    int l;
    int r;
    int max;
    int t;

    l=2*i+1;
    r=2*i+2;

    if ((l<heapsize) && (a[l]>a[i])) max=l;
    else max=i;

    if ((r<heapsize) && (a[r]>a[max])) max=r;

    if (max!=i)
    {
        t=a[max];
        a[max]=a[i];
        a[i]=t;
        heapify(max);
    }
}

void __fastcall TForm1::btnSortClick(TObject *Sender)
{
    int k;
    elements=lbItems->Items->Count-1;

    for (k=0;k<=elements;k++) a[k]=lbItems->Items->operator
[](k).ToInt();
    heapsort();

    Form2->lbSorted->Items->Clear();
    for (k=0;k<=elements;k++)
    {
        Form2->lbSorted->Items->Add(AnsiString(a[k]));
    }

    Form2->ShowModal();
}
void __fastcall TForm1::btnClearClick(TObject *Sender)
{
    lbItems->Items->Clear();
}
void __fastcall TForm1::btnAddClick(TObject *Sender)
{
    AnsiString value;
    InputQuery("Add value","Value",value);
    lbItems->Items->Add(value);
}
void __fastcall TForm1::btnExitClick(TObject *Sender)
{
    Close();
}

[Reegan]

You can also use the following coding for the Heap Code in C++ programming language :

header file:
#ifndef HEAP_H
#define HEAP_H
class heap
{
friend ostream &operator<<( ostream&, const heap & );
private:
Type *array;
int MaxSize, Nel;
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);
bool DelMax(Type& item);
};
#endif

cpp file:
#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;
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;

} 

if ( i % 4 != 0 ) // end last line of output
output << endl;

return output; // enables cout << x << y;

}

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 )
{
if ( MaxSize != right.size )
{
delete [] array; // reclaim space
MaxSize = right.MaxSize; 
array = new int[ MaxSize ];
} 
for ( int i = 0; i < MaxSize; i++ )
array[ i ] = right.array[ i ];
} 
return *this;
} 

int &heap::operator[]( int subscript )
{
if ( subscript < 0 || subscript >= MaxSize ) {
cout << "\nError: Subscript " << subscript
<< " out of range" << endl;
exit( 1 );
}
return array[ subscript ];
} 

bool heap::Insert(Type 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)
{
int j = 2*i, item = a[i];
while (j <= n)
{
if ((j<n) && (a[j]<a[j+1]))
j++;
if (item >= a[j])
break;
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;
};

[Pratim]

Extremely thanks for you guys for trying to solve my issue. I have copied the coding as mentioned by the 'Zecho' but I am getting an error. The Error was "[C++ Error] Unit1.cpp[76]:E2316 'operator[]' is not a member of
'TStrings'" with the line:
a[k]=lbItems->Items->operator[](k).ToInt();"
I don't know how fix this error. I am using the Bourland C++. Please help me further also. Once again Thanks for helping me.

[Zecho]

Actually I was using the C++Builder 6 with the new extensions for running the program. You will have to change the line

for (k=0;k<=elements;k++) a[k]=lbItems->Items->operator

to

for (k=0;k<=elements;k++) a[k]=lbItems->Items->Strings[k].ToInt();

Also don't forget to use the Form resources. Hope that changing the code will help you to fix the Error.