Binary Heap Implementation Using a Binary Tree
My Java AP AB teacher has set forth a challenge:
As a group, the four students in my class must implement a Priority Queue using a binary heap. This heap, however, needs to be implemented using a binary tree, without storing it in an array. It's more of a wager than an assignment; we are allowed to find a solution by any means necessary and have to buy him breakfast if we don't.
He's not sure it can be done. Our biggest frustration, of course, is in the implementation of the heap--specifically the insert method. The problem with a binary tree is that any given node is aware only of its children--we can't go across the tree.
Wikipedia claims it's possible:
"It is perfectly possible to use a traditional binary tree data structure to implement a binary heap. There is an issue with finding the adjacent element on the last level on the binary heap when adding an element which can be resolved algorithmically or by adding extra data to the nodes, called "threading" the tree ?that is, instead of merely storing references to the children, we store the inorder successor of the node as well."
(from http://en.wikipedia.org/wiki/Binary_heap#Heap_implementation)
The latter solution is not an option for this project. How, specifically, would one "algorithmically resolve" this problem? I've been trying for days to write such an algorithm with little success. Any help, suggestions, code, links, ideas, etc. would be greatly appreciated.
[1492 byte] By [
stellanora] at [2007-10-2 12:35:21]
There are many ways to do what you propose, though as often happens your description is a bit vague, not through any fault of yours but because when you are solving a problem "with one hand tied behind your back" on a bet, you need to be clear about what the real limitations are.
For example, do your binary trees have back pointers from a node to its parent or are we talking about REAL binary trees where you only point from parent to node. Twould help to know something like that.
For example, RippleUp is easy with a pointer to the parent otherwise, you must traverse downward and ripple up on the way back up through the return stack.
Also, are you allowed to keep even one extra integer, not one per node, just one extra, like the size of the heap? That would make it easier to find the end of the tree. Well, not easier, faster. But I know, the answer is probably no.
So how do you find the end of the tree. Given its regular shape it is fairly easy. Consider a fairly standard inOrder tree traversal, the one where you print the left sub tree, then the parent, then the right subtree. Modify the algorithm ever so slightly to count the depth on its way down and print the depth along with the node.
Notice that the last row of the heap has the maximum depth number and notice that the actual end of the heap (last element in the heap) is the very last element of maximum depth that you will cross in the traversal.
Now, where is the next empty space, the one where you will need to add a new element?
Could be in one of three places.
1) you could have had a perfectly balanced binary tree and you need to introduce a new node all the way over on the the left of the left of the left.
You will detect this by having run into the very last element of the heap as the very last element of the traversal.
2) the last element could have been a left child in which case you need to add a right child (and notice that the parent would have been the node exactly following the last node in your inOrder traversal
3) the last element could have been a right child. In this case, the very next element in the inOrder traversal is some great great grandparent of the last node (and the path to the last node starting from that ancestor must have been a single left followed by some number of rights) The place you want to hang the new node will be to go right from that grandparent and then as many lefts as you can do.
You pretty much have to draw the pictures if you want to see what I am talking about. But with the pictures in hand, you can see where you must hang the next element. It is then a fairly simple matter to hang the new element in its place and ripple up.
In fact, since you can detect the place that you need to hang the next element exactly when you are sitting on the parent node where you must put that element, and furthermore you are deeply down in a recursive routine that holds a stack trace of all the parents that got you there, you can do the ripple up on your way back out of the tree traversal.
Here's a concrete example showing the tree traversal
3A 2B 3C 1D 2E
the first element was A at depth 3 so you know that is the max depth. following it is node B, A's parent the next node C is also at depth 3 so is the new candidate for being the end of the heap. The next node D is the root of the tree and the ancestor of C (who was a right child) the next node E is NOT at the max depth SO, you know that it is the place to do the insert , the left child of E.
Piece of cake!
And for the record, a complete waste of time. The purpose of a heap is of course to enjoy the small storage because of the lack of explicit pointers and to also enjoy the time saved by doing everything in O(lg(n)) time. By doing it in a binary tree, you have wasted all the space for the pointers and by refusing to store even the size of the heap you force a search for the end on every insert and have thus converted an insert to an O(N) operation.
Don't buy him breakfast!!!
That is great. Thank you so much.
I'm sorry for my lack of specificity before: yes, no fields that point to the parent are allowed. The nodes hold just an object and two children nodes. However, I think a count or size field is reasonable. In other words, I think we're allowed do whatever we want in this class we're designing, we just can't meddle with the nodes themselves. It needs to be a binary tree.
I'll take your suggestions to the drawing board (literally) today. Thanks again for your help. I realize this is a pointless, ineffective pursuit with no real-world application--but that's high school programming, I guess.
I got a bit lost in there somewhere... :-/
You don't need to walk the whole tree to find the biggest (or smallest) value in the tree.
If you assume that the children to the left of the parent are <= the parent, and the children to the right are > the parent, then the following holds:
Assuming there are lots of nodes in the tree, then everything to the right of the root is greater than the root. So the biggest value must be to the right of the root. Then apply this argument recursively until you reach a node which has no right children. It must be the largest node.
That is, start at the root, and continually follow the right pointer until there is no right pointer. You are now at the largest node.
The same logic applies to the smallest value in the tree... simply go left from the root until you can go left no more.
The place that you got lost is that a heap ordering is different from a sort ordering. It is NOT the case in a heap that the values in the left node are less than the root and the values in the right are greater than the root.
In a heap, the children to the left AND the children to the right are less than the root. The root always holds the MAX value in a heap.
Also when you are looking to insert into a heap, you are not looking for a max or a min value in the heap, rather you are looking for a place in the tree shape. You are looking for an empty slot at the end of that special tree shape.
The shape of a heap is essentially the largest possible COMPLETE binary tree (where all internal nodes have both child nodes) which in necessarily a power of 2 minus 1 nodes, and then you fill in along the bottom row of that complete tree with the ramaining nodes. Thus the tree has as uniform a depth as possible, with the excess depth skewed to the left.
The stuff about running the inOrder traversal was to find that place where the depth of the tree was one less than the maximum so that you could see where to insert.
Finally for the OP, IF you are allowed to store the total count of the heap in the class, then you can get back to the O(lg(n)) behavior. You do not need to traverse the entire tree to get to the end of the heap. Because the count tells you exactly what the shape of the tree must have been, you can thus decode the count (work it out for your self - it is a cute problem) on you way down the tree to get to the exact place where you need to be for your insert. You then rippleUp back through the stack trace to place the element correctly
Or looked at differently, you know that the element that you are adding to the heap is going to go somewhere on the chain that you are passing through on your way to the empty slot at the end. So on you way down, you can notice where it belongs, echange it, and propagate the loser on downwards. So you don't really need to do a rippleUp on the way back, you can do the rippleUp on the way down.
whew!
