Want to protect your cyber security and still get fast solutions? Ask a secure question today.Go Premium

x
• Status: Solved
• Priority: Medium
• Security: Public
• Views: 2149

# 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 .

0
kitrobin
• 4
• 2
1 Solution

Commented:
http://en.wikipedia.org/wiki/Binary_heap

Look at the paragraph "adding to the heap"
0

Author Commented:
How will I add from the bottom? I am using a pointer to the root.Still very confused
0

Commented:
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.
0

Author Commented:
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;
}
0

Commented:
>>             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
0

Commented: