I currently need to implement a max heap of nodes where my node class keeps track of the data, the parent and then the left and right child. My insert method for max heap is taking forever to fill with an array of 100 strings. Here is my code: `
public void insert(String name) {
MyNode node = new MyNode(name);
if (root ==null) {
root = node;
}
else {
MyNode parent = findSpot(root);
if(parent.lChild==null) {
parent.lChild=node;
node.setParent(parent);
}
else {
parent.rChild=node;
node.setParent(parent);
}
}
}
public MyNode findSpot(MyNode curr) {
if (curr.lChild == null) {
return curr;
}
else if (curr.rChild==null) {
return curr;
}
else {
if (findSpot(curr.lChild).findHeight(root, curr, 1) > findSpot(curr.rChild).findHeight(root, curr, 1)) {
return findSpot(curr.lChild);
}
else {
return findSpot(curr.rChild);
}
}
}`
If anyone code offer suggestions or tell me whats wrong that'd be greatly appreciated.
If you want to see why your findSpot function is taking so long, add a line at the beginning that outputs "findSpot <node>", where is the details of the node being searched. You'll find that the recursive algorithm is being called many times. And it looks like findHeight is also being called quite often. I'm not certain, but it looks like you're doing an exhaustive tree search on every insertion.
Binary heaps must maintain the Shape property: it is a complete binary tree except possibly the bottom row, which is left-filled. Because of that, if you know how many nodes are in your heap, you can easily find the insertion spot for the next node. Consider this heap:
1
2 3
4 5 6
There are 6 nodes in the heap. Whenever there are 6 nodes in a heap, the tree will look like this and the insertion spot for the next node will be the right child of the far right node (3 in this case).
The interesting thing is that the binary representation of the node number tells us where that node is. For example, 6 in binary is 110. Lop off the first digit, 1, and you're left with 10. Now, starting at the root and taking the next digit in the number, go left if the digit is 0, and right if the digit is 1. Then take the next digit and do the same thing. Repeat until you run out of digits.
In the case of 6, we'd go right from the root to node 3, and then left to node 6.
When you're adding a new node, increment the count and follow the procedure above to locate the insertion spot. 7 is 111 in binary. You lop off the high bit, leaving 11. Then, starting at the root you go right, and the insertion spot is the right child of node 3.
Of course, once you've placed the node in the tree to satisfy the shape property, you have to do the standard re-heapify to adjust the nodes in the tree so that the heap property is maintained.