Just a sidenote!
in the add function should be like this:
When the left pointer is not null and the right pointer is nullCode: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); } }
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!
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.
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: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:Code:0 / \ 2 1 / \ / \ 3 5 4
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 01: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"
