kitrobin
asked on
Heapify Binary tree insertion
I have an insertion function for a binary tree is it possible to convert it to a Binary Heap instead.The element I am inserting are contained in a Node class with data members of id , name etc
if ( *ptr == NULL ) // tree is empty
{
*ptr = new Node( id, name);
}
else // tree is not empty
if ( id < (( *ptr )->idno ))
insertHelper( &( (*ptr)->leftPtr ), id, name );
else
if ( id > (( *ptr )->idno ))
insertHelper( &( ( *ptr )->rightPtr ), id, name);
}//helper takes in a root pointer of type Node* and data members .
if ( *ptr == NULL ) // tree is empty
{
*ptr = new Node( id, name);
}
else // tree is not empty
if ( id < (( *ptr )->idno ))
insertHelper( &( (*ptr)->leftPtr ), id, name );
else
if ( id > (( *ptr )->idno ))
insertHelper( &( ( *ptr )->rightPtr ), id, name);
}//helper takes in a root pointer of type Node* and data members .
ASKER
How will I add from the bottom? I am using a pointer to the root.Still very confused
That's answered in the "Heap implementation" paragraph on the same page.
One approach is to keep a reference to the next sibling on the same level for each node. Alternatively, you can keep the heap in an array, so you don't need pointers.
One approach is to keep a reference to the next sibling on the same level for each node. Alternatively, you can keep the heap in an array, so you don't need pointers.
ASKER
Ok.I tried using an array with an example from a text but I can't seem to modify it to work with Node elements
class BinaryHeap
{
public:
BinaryHeap( int capacity = 100 );
void insert( long, char[], char[], char[],int, char[], int, char[]);
void delete( );
private:
int currentSize; // Number of elements in heap
Node* array; // The heap array
void buildHeap( );
void percolateDown( int hole );
};
BinaryHeap::BinaryHeap( int capacity )
: array( capacity + 1 ), currentSize( 0 )
{
}
void BinaryHeap::insert( long id, char fname[], char lname[], char pay[], int day,
char rmType[], int rmNo, char reason[] )
{
array =new Node(id, fname, lname, pay, day, rmType, rmNo, reason);
int hole = ++currentSize;
for( ; hole > 1 && id < array[ hole / 2 ]; hole /= 2 )
array[ hole ] = array[ hole / 2 ];
array[ hole ] = id;
}
class BinaryHeap
{
public:
BinaryHeap( int capacity = 100 );
void insert( long, char[], char[], char[],int, char[], int, char[]);
void delete( );
private:
int currentSize; // Number of elements in heap
Node* array; // The heap array
void buildHeap( );
void percolateDown( int hole );
};
BinaryHeap::BinaryHeap( int capacity )
: array( capacity + 1 ), currentSize( 0 )
{
}
void BinaryHeap::insert( long id, char fname[], char lname[], char pay[], int day,
char rmType[], int rmNo, char reason[] )
{
array =new Node(id, fname, lname, pay, day, rmType, rmNo, reason);
int hole = ++currentSize;
for( ; hole > 1 && id < array[ hole / 2 ]; hole /= 2 )
array[ hole ] = array[ hole / 2 ];
array[ hole ] = id;
}
>> BinaryHeap::BinaryHeap( int capacity )
>> : array( capacity + 1 ), currentSize( 0 )
array is a pointer to Node - you can't initialize it to an integer value ... You need to allocate memory for capacity amount of nodes.
The insert will have to be a bit different too.
You can take a look at this example :
http://library.thinkquest.org/C005618/text/heaps.htm
>> : array( capacity + 1 ), currentSize( 0 )
array is a pointer to Node - you can't initialize it to an integer value ... You need to allocate memory for capacity amount of nodes.
The insert will have to be a bit different too.
You can take a look at this example :
http://library.thinkquest.org/C005618/text/heaps.htm
ASKER CERTIFIED SOLUTION
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
Look at the paragraph "adding to the heap"