Heaps!

This is a discussion on Heaps! within the C Programming forums, part of the General Programming Boards category; Just a sidenote! in the add function should be like this: Code: void add(int x, node** root){ node* new_node = ...

  1. #16
    Registered User
    Join Date
    Apr 2008
    Posts
    103
    Just a sidenote!
    in the add function should be like this:
    Code:
    void add(int x, node** root){
                                node* new_node = (node*) malloc(sizeof(node));
                                if (*root == NULL){
                                   *root = new_node;
                                   (*root)->data = x;
                                   (*root)->left = NULL;
                                   (*root)->right = NULL;
                                   }
                                else{
                                     if((*root)->left != NULL && (*root)->right == NULL)
                                                         add(x,&((*root)->right));
                                     else
                                                         add(x,&(*root)->left);
                                     }
         }
    When the left pointer is not null and the right pointer is null

  2. #17
    Registered User
    Join Date
    Apr 2008
    Posts
    103
    I just realized that the function that adds numbers to the tree does not actually preserve the complete tree property! I really thought it was working!
    It works for the first level (zero being the level of root), but then it just keeps going to the left!
    It turns out I'm having a more basic problem !
    Need help!

  3. #18
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    If you want to keep it balanced, you would need to keep track of how deep each side is, not whether or not each side exists. IOW, if both sides exist, now you have to get a depth of each node and use that to choose.

  4. #19
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,308
    Okay, I'm home from work...
    Whilst it seems simple enough to represent a heap using a binary tree in theory, it does have some additional difficulties over the array version.
    For example, the normal way of removing an item from the top of the heap would be to copy away the top item and overwrite it with the last item in the array. When you've got a tree though, that becomes difficult. Difficult, but not impossible. First we need an example:
    Code:
            0
          /   \
         2     1
        / \   / \
       3  5  4
    This heap has 6 items. To pop an item from the top, we need to replace the 0 with the 4 and reheapify. The trick to finding that node is:
    Examine the number of items in the tree in binary:
    6 (base 10) = 110 (base 2)
    Now, you throw away the leftmost 1, giving:
    10
    Now, do down through the tree with 1 meaning go right, and 0 meaning go left.
    So, right from zero takes us to the one, then left from the one takes us to the four. Of course we detach the four from the one while we're there and then copy the pointer links from the zero being popped off the head, into the pointer links in the four node.

    Now upon removing that node the count is 5. That's 101 in binary, so ignoring the top bit, that's a left then a right.
    Next the count if 4. That's 100 in binary, so ignoring the top bit, that's a left then a left.
    Next the count if 3. That's 11 in binary, so ignoring the top bit, that's a right, then stop.
    etc...
    Until where you don't have a top bit in the binary representation of zero, so there is nothing left you can remove.

    When it comes to adding nodes, the same technique of using the binary representation of the new size can also be used to find the place to add the new node, thus keeping the heap perfectly balanced.

    Edit: Oh and I nearly forgot to mention, it'll perform like a dog compared to the array version. Slower and more memory hungry, and it takes quite a bit more code. I think you'll agree by now that arrays and heaps were meant for each other.
    Last edited by iMalc; 11-26-2008 at 12:44 AM.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

Page 2 of 2 FirstFirst 12
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Buffers , heaps , stacks ...
    By BlaX in forum Tech Board
    Replies: 9
    Last Post: 02-17-2009, 02:09 PM
  2. Buffers , heaps , stacks ...
    By BlaX in forum C Programming
    Replies: 1
    Last Post: 02-17-2009, 12:11 PM
  3. Using Shared Heaps
    By drwho in forum C Programming
    Replies: 4
    Last Post: 12-30-2005, 03:25 PM
  4. Help with heaps?
    By Nornny in forum C++ Programming
    Replies: 4
    Last Post: 03-22-2004, 11:19 AM
  5. FAQ heaps
    By face_master in forum FAQ Board
    Replies: 2
    Last Post: 10-06-2001, 11:21 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21