Want to win a PS4? Go Premium and enter to win our High-Tech Treats giveaway. Enter to Win

x
Solved

Heapify Binary tree insertion

Posted on 2007-11-18
Medium Priority
2,147 Views
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
Question by:kitrobin
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

• Help others & share knowledge
• Earn cash & points
• 4
• 2

LVL 53

Expert Comment

ID: 20307717
http://en.wikipedia.org/wiki/Binary_heap

Look at the paragraph "adding to the heap"
0

Author Comment

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

LVL 53

Expert Comment

ID: 20308110
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 Comment

ID: 20308165
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

LVL 53

Expert Comment

ID: 20308223
>>             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

LVL 53

Accepted Solution

Infinity08 earned 600 total points
ID: 20308226

http://www.cs.fiu.edu/~weiss/dsaa_c++/code/
0

Featured Post

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

In this post we will learn how to make Android Gesture Tutorial and give different functionality whenever a user Touch or Scroll android screen.
Looking for a way to avoid searching through large data sets for data that doesn't exist? A Bloom Filter might be what you need. This data structure is a probabilistic filter that allows you to avoid unnecessary searches when you know the data definâ€¦
The viewer will be introduced to the technique of using vectors in C++. The video will cover how to define a vector, store values in the vector and retrieve data from the values stored in the vector.
Six Sigma Control Plans
Suggested Courses
Course of the Month8 days, 18 hours left to enroll