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
  • Last Modified:

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
Asked:
kitrobin
  • 4
  • 2
1 Solution
 
Infinity08Commented:
       http://en.wikipedia.org/wiki/Binary_heap

Look at the paragraph "adding to the heap"
0
 
kitrobinAuthor Commented:
How will I add from the bottom? I am using a pointer to the root.Still very confused
0
 
Infinity08Commented:
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
Technology Partners: We Want Your Opinion!

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

 
kitrobinAuthor 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
 
Infinity08Commented:
>>             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
 
Infinity08Commented:
or the one on this page :

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

Featured Post

What does it mean to be "Always On"?

Is your cloud always on? With an Always On cloud you won't have to worry about downtime for maintenance or software application code updates, ensuring that your bottom line isn't affected.

  • 4
  • 2
Tackle projects and never again get stuck behind a technical roadblock.
Join Now