Solved

Heapify Binary tree insertion

Posted on 2007-11-18
6
2,127 Views
Last Modified: 2012-08-14
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
Comment
Question by:kitrobin
  • 4
  • 2
6 Comments
 
LVL 53

Expert Comment

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

Look at the paragraph "adding to the heap"
0
 

Author Comment

by:kitrobin
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

by:Infinity08
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
Is Your Active Directory as Secure as You Think?

More than 75% of all records are compromised because of the loss or theft of a privileged credential. Experts have been exploring Active Directory infrastructure to identify key threats and establish best practices for keeping data safe. Attend this month’s webinar to learn more.

 

Author Comment

by:kitrobin
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

by:Infinity08
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

by:
Infinity08 earned 200 total points
ID: 20308226
or the one on this page :

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

Featured Post

Is Your Active Directory as Secure as You Think?

More than 75% of all records are compromised because of the loss or theft of a privileged credential. Experts have been exploring Active Directory infrastructure to identify key threats and establish best practices for keeping data safe. Attend this month’s webinar to learn more.

Question has a verified solution.

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

Whether you’re a college noob or a soon-to-be pro, these tips are sure to help you in your journey to becoming a programming ninja and stand out from the crowd.
Computer science students often experience many of the same frustrations when going through their engineering courses. This article presents seven tips I found useful when completing a bachelors and masters degree in computing which I believe may he…
The goal of the tutorial is to teach the user how to use functions in C++. The video will cover how to define functions, how to call functions and how to create functions prototypes. Microsoft Visual C++ 2010 Express will be used as a text editor an…
The viewer will learn how to pass data into a function in C++. This is one step further in using functions. Instead of only printing text onto the console, the function will be able to perform calculations with argumentents given by the user.

867 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question

Need Help in Real-Time?

Connect with top rated Experts

20 Experts available now in Live!

Get 1:1 Help Now