geekitarian

Think about this MaxHeap: 0 1 2 3 4 5 6 23 12 19 7 10 18 14 Remember, children are found with this formula: Left child: 2i + 1 Right child: 2i + 2 Parents are found with this formula: Parent: (i - 1) / 2 If we have a maxheap, the children are smaller than the parents.  If we have a minheap, the children are larger than the parents.  This is a maxheap, so all parents are larger than their children. To add to a maxheap, we put the new value at the next available position in the array then swap up.  In the file for your assignment, we call this process reheapUp. If we add the value 20 to the maxheap above, we get this: 0 1 2 3 4 5 6 7 23 12 19 7 10 18 14 20 We swap 20 (index 7) with its parent, if the parent is smaller.  The parent value is 7 (index 3) so we swap up. 0 1 2 3 4 5 6 7 23 12 19 20 10 18 14 7 We swap 20 (index 3) with its parent, if

Let’s say we already have a binary tree, and we want to build an Iterator to return the nodes in our tree in order.  If we were just listing the nodes, we could follow this recursive algorithm: Go to the left child (if it exists) Output the current node Go to the right child (if it exists) Consider this tree: We would start at the root (M); we’d immediately go to the left (F), then go to the left again (A).  There are no more values to go to the left, so we’d output the current node (A).  Then we’d go to the right - but there’s nothing to the right of A.  So we’d return.  This would return us to the previous level of recursion, where we’d output the current node (F).  We’d then go to the right (K); the next step would be to go to the left (J), then go to the left again (G).  We’d then output G as there’s no further left to go to; there’s nothing to the right, so we’d return to previous level of recursion (J).  We’d output J, and so on.  Eventually we’d output the va