Hw problem, algorithm with binaryheap

[chrisbull]

Alright i've been trying to figure this out for a while now. I'm trying to do the first step of my homework, this is what it says.

"Read in the file “RomeoAndJuliet.txt”. Ignore any empty lines and trim any leading whitespace. Store the entire line as a string in your data structure. Record how many data points each of your structures stored, e.g., 4000 lines (AVL tree), … You should have 5 data points, one for each structure."

My data structure i'm using is going to be BinaryHeap, I was given a .h file which contains:



#ifndef BINARY_HEAP_H
#define BINARY_HEAP_H


#include "dsexceptions.h"
#include <vector>

using namespace std;

// BinaryHeap class
//
// CONSTRUCTION: with an optional capacity (that defaults to 100)
//
// ******************PUBLIC OPERATIONS*********************
// void insert( x ) --> Insert x
// deleteMin( minItem ) --> Remove (and optionally return) smallest item
// Comparable findMin( ) --> Return smallest item
// bool isEmpty( ) --> Return true if empty; else false
// void makeEmpty( ) --> Remove all items
// ******************ERRORS********************************
// Throws UnderflowException as warranted

template <typename Comparable>
class BinaryHeap
{
public:
explicit BinaryHeap( int capacity = 100 )
: array( capacity + 1 ), currentSize{ 0 }
{
}

explicit BinaryHeap( const vector<Comparable> & items )
: array( items.size( ) + 10 ), currentSize{ items.size( ) }
{
for( int i = 0; i < items.size( ); ++i )
array[ i + 1 ] = items[ i ];
buildHeap( );
}

bool isEmpty( ) const
{ return currentSize == 0; }

/**
* Find the smallest item in the priority queue.
* Return the smallest item, or throw Underflow if empty.
*/
const Comparable & findMin( ) const
{
if( isEmpty( ) )
throw UnderflowException{ };
return array[ 1 ];
}

/**
* Insert item x, allowing duplicates.
*/
void insert( const Comparable & x )
{
if( currentSize == array.size( ) - 1 )
array.resize( array.size( ) * 2 );

// Percolate up
int hole = ++currentSize;
Comparable copy = x;

array[ 0 ] = std::move( copy );
for( ; x < array[ hole / 2 ]; hole /= 2 )
array[ hole ] = std::move( array[ hole / 2 ] );
array[ hole ] = std::move( array[ 0 ] );
}


/**
* Insert item x, allowing duplicates.
*/
void insert( Comparable && x )
{
if( currentSize == array.size( ) - 1 )
array.resize( array.size( ) * 2 );

// Percolate up
int hole = ++currentSize;
for( ; hole > 1 && x < array[ hole / 2 ]; hole /= 2 )
array[ hole ] = std::move( array[ hole / 2 ] );
array[ hole ] = std::move( x );
}

/**
* Remove the minimum item.
* Throws UnderflowException if empty.
*/
void deleteMin( )
{
if( isEmpty( ) )
throw UnderflowException{ };

array[ 1 ] = std::move( array[ currentSize-- ] );
percolateDown( 1 );
}

/**
* Remove the minimum item and place it in minItem.
* Throws Underflow if empty.
*/
void deleteMin( Comparable & minItem )
{
if( isEmpty( ) )
throw UnderflowException{ };

minItem = std::move( array[ 1 ] );
array[ 1 ] = std::move( array[ currentSize-- ] );
percolateDown( 1 );
}

void makeEmpty( )
{ currentSize = 0; }

private:
int currentSize;
vector<Comparable> array;

/**
* Establish heap order property from an arbitrary
* arrangement of items. Runs in linear time.
*/
void buildHeap( )
{
for( int i = currentSize / 2; i > 0; --i )
percolateDown( i );
}

/**
* Internal method to percolate down in the heap.
* hole is the index at which the percolate begins.
*/
void percolateDown( int hole )
{
int child;
Comparable tmp = std::move( array[ hole ] );

for( ; hole * 2 <= currentSize; hole = child )
{
child = hole * 2;
if( child != currentSize && array[ child + 1 ] < array[ child ] )
++child;
if( array[ child ] < tmp )
array[ hole ] = std::move( array[ child ] );
else
break;
}
array[ hole ] = std::move( tmp );
}
};

#endif



From what I understand I have to read in the file 'romeo and juliet'. Which is just text from the book, so i've managed to read in the text file using fstream and store it in a string called line. Here is my main method so far.

#include <algorithm>
#include <stdexcept>
#include "BinaryHeap.h"

using namespace std;

int main () {
string line;


ifstream myfile ("RomeoAndJuliet.txt");
if (myfile.is_open())
{
while ( getline (myfile,line) )
{
BinaryHeap<string> H
H.deleteMin(line);


}
myfile.close();
}

else cout << "Unable to open file";

return 0;
}

readin.cpp:26:4: error: expected initializer before ‘H’
H.deleteMin(line);

obviously i'm getting an error when compiling because its wrong, i'm not sure what to put in place of the 'H' after string and before .deletemin. The error I get is above, hopefully i've explained it enough for you to understand, I'm not even 100% on it myself yet so that's why my explanation is a little vague.

[DEnumber50]

Make sure you use the source code tag when posting code, makes it a lot easier to read.

#ifndef BINARY_HEAP_H
#define BINARY_HEAP_H

#include "dsexceptions.h"
#include <vector>
using namespace std;
// BinaryHeap class
//
// CONSTRUCTION: with an optional capacity (that defaults to 100)
//
// ******************PUBLIC OPERATIONS*********************
// void insert( x ) --> Insert x
// deleteMin( minItem ) --> Remove (and optionally return) smallest item
// Comparable findMin( ) --> Return smallest item
// bool isEmpty( ) --> Return true if empty; else false
// void makeEmpty( ) --> Remove all items
// ******************ERRORS********************************
// Throws UnderflowException as warranted

template <typename Comparable>
class BinaryHeap
{
public:
explicit BinaryHeap( int capacity = 100 )
: array( capacity + 1 ), currentSize{ 0 }
{
}

explicit BinaryHeap( const vector<Comparable> & items )
: array( items.size( ) + 10 ), currentSize{ items.size( ) }
{
for( int i = 0; i < items.size( ); ++i )
array[ i + 1 ] = items[ i ];
buildHeap( );
}

bool isEmpty( ) const
{ return currentSize == 0; }

/**
* Find the smallest item in the priority queue.
* Return the smallest item, or throw Underflow if empty.
*/
const Comparable & findMin( ) const
{
if( isEmpty( ) )
throw UnderflowException{ };
return array[ 1 ];
}

/**
* Insert item x, allowing duplicates.
*/
void insert( const Comparable & x )
{
if( currentSize == array.size( ) - 1 )
array.resize( array.size( ) * 2 );

// Percolate up
int hole = ++currentSize;
Comparable copy = x;

array[ 0 ] = std::move( copy );
for( ; x < array[ hole / 2 ]; hole /= 2 )
array[ hole ] = std::move( array[ hole / 2 ] );
array[ hole ] = std::move( array[ 0 ] );
}


/**
* Insert item x, allowing duplicates.
*/
void insert( Comparable && x )
{
if( currentSize == array.size( ) - 1 )
array.resize( array.size( ) * 2 );

// Percolate up
int hole = ++currentSize;
for( ; hole > 1 && x < array[ hole / 2 ]; hole /= 2 )
array[ hole ] = std::move( array[ hole / 2 ] );
array[ hole ] = std::move( x );
}

/**
* Remove the minimum item.
* Throws UnderflowException if empty.
*/
void deleteMin( )
{
if( isEmpty( ) )
throw UnderflowException{ };

array[ 1 ] = std::move( array[ currentSize-- ] );
percolateDown( 1 );
}

/**
* Remove the minimum item and place it in minItem.
* Throws Underflow if empty.
*/
void deleteMin( Comparable & minItem )
{
if( isEmpty( ) )
throw UnderflowException{ };

minItem = std::move( array[ 1 ] );
array[ 1 ] = std::move( array[ currentSize-- ] );
percolateDown( 1 );
}

void makeEmpty( )
{ currentSize = 0; }

private:
int currentSize; 
vector<Comparable> array; 

/**
* Establish heap order property from an arbitrary
* arrangement of items. Runs in linear time.
*/
void buildHeap( )
{
for( int i = currentSize / 2; i > 0; --i )
percolateDown( i );
}

/**
* Internal method to percolate down in the heap.
* hole is the index at which the percolate begins.
*/
void percolateDown( int hole )
{
int child;
Comparable tmp = std::move( array[ hole ] );

for( ; hole * 2 <= currentSize; hole = child )
{
child = hole * 2;
if( child != currentSize && array[ child + 1 ] < array[ child ] )
++child;
if( array[ child ] < tmp )
array[ hole ] = std::move( array[ child ] );
else
break;
}
array[ hole ] = std::move( tmp );
}
};

#endif



From what I understand I have to read in the file 'romeo and juliet'. Which is just text from the book, so i've managed to read in the text file using fstream and store it in a string called line. Here is my main method so far.

#include <algorithm>
#include <stdexcept>
#include "BinaryHeap.h"


using namespace std;

int main () {
string line;


ifstream myfile ("RomeoAndJuliet.txt");
if (myfile.is_open())
{
while ( getline (myfile,line) )
{
BinaryHeap<string> H
H.deleteMin(line);


}
myfile.close();
}

else cout << "Unable to open file";

return 0;
}

readin.cpp:26:4: error: expected initializer before ‘H’
H.deleteMin(line); 

[fg109]

I believe the error is in regards to your missing semicolon.