Duke Computer Science Shield

CompSci 201: Data Structures & Algorithms

Recitation

Fall 2012

 

Recitation 10:
Recursive Backtracking, Priority Queues, and Heaps. Oh My!

November 9, 2012

 





Recursive Backtracking

Open your recitation 8 code and look at TreeNodeExample.java. You are going to add the recursive backtracking method, GetPathWithSum as defined below.

To be able to test your code, you should add the following lines of code to main. TreeNodeExample tree = new TreeNodeExample(); int[] numsToAdd = {9,5,14,3,7,12,18,4,11,13}; for(int i: numsToAdd){ tree.add(i); } Stack<Integer> path = tree.getPathSum(23); for(Integer i: path) System.out.print(i + " ");

  1. From the code above, draw the binary search tree (BST) that the code creates. Your tree is initially empty and the nodes are added following the binary search tree rules.








Add the following code to IntTreeNode.java and complete the recursive backtracking function. (Hint: it has lots of helpful comments in it.) getPathSum(23) should print out 9 14 (Make sure this agrees with the tree you drew above.) public Stack<Integer> getPathSum(int target){ getPathSum(root, target); return myPath; } //store your path here Stack<Integer> myPath = new Stack<Integer>(); private boolean getPathSum(IntTreeNode t, int target){ //your base cases go here //add the current value to your path //can you build the path going left? //can you build the path going right? //if not BACKTRACK!!! }

Priority Queues

Snarf the code for todays class. You will find the code, RunningJobs.java.

Say you have a whole bunch of little jobs that you need to get done. You wrote them all done and you know how long each will take. You want to be able to get the most number of little jobs done as possible, however some are more important to get done than others. This is when a priority queue is great. Complete the code RunningJobs that puts a collection of jobs into a priority queue with their time to complete and priority. Compute the maximum number of jobs you can get done assuming that you need to complete the high priority jobs first.

Hints: Complete your compareTo and use a priority queue. There is a toString method in Jobs that may be helpful for debugging.

Heap Questions

A binary heap is a method of storing a binary tree in an array when the binary tree maintains two properties:

  • The heap shape: the binary tree must be a complete tree, that is every level of the tree is full/complete except perhaps for the last level which is filled in from left to right.

  • The heap property: every node is smaller than its two children.

    The tree shown below on the left has both the heap shape and the heap property.

    Binary trees that are heaps are typically stored in an array. The root of the tree has index one (the array element with index zero isn't used). The children of the root are at indexes two (left child) and three (right child). In general, the children of the tree node with index k have indexes 2k (left child) and 2k+1 (right child).

    The binary tree on the left below is stored in a vector as shown on the right.

    Conceptual Heap Heap in array


    Questions About Heaps

    1. Where is the smallest element in a heap (and why?)

    2. Where is the largest element in a heap (and why?)

    3. Where is the parent of the element with index 11 when a heap is stored in an array ?

    4. Where is the parent of the element with index k when a heap is stored in an array?

    5. If the value 19 in the heap above is changed to 25, is the heap property maintained?

    6. If the value 21 in the heap above is changed to 13, is the heap property maintained?

    7. If a new node with 19 is added as the left child of 17 in the heap above, is the heap shape maintained?



      Adding an element to a Heap



      When a new element is added to a heap, both the heap shape and the heap property must be maintained. To maintain the shape, the new element must be added as the last element of the array (why?). This may violate the heap property, so all nodes on the path from the root to the newly added leaf must be checked to see where the new value really belongs, starting from the leaf.

      This process is shown below for adding the value 12 to the heap shown above.

      First, the 12 is shown on the left added to maintain the heap shape. However, the 12 doesn't belong there (the heap property is violated) so the yellow node is shown on the right with no value, the newly added value 12 is "waiting" to find its place as all nodes on the path from the newly added leaf to the root are examined to find where the 12 belongs.


      In the diagram above on the right, the 12 can't stay as a leaf, so the value in node above it is moved down to the leaf, and the yellow node conceptually moves up -- this is a new tentative spot for the 12 as shown on the left below.



      The 12 cannot stay in the location shown above on the left since it is less than 15. The 15 is moved down to the yellow node, and the yellow node conceptually moves up -- this is the tentative spot for the 12 as shonw above on the right.

      The 12 belongs as the childe of 7 (the root) since it is less than the root. The final tree is shown below. The newly-added 12 has been moved up from its original tentative location as a leaf (where the 21 is below) to its final location.



      Questions About Adding Values to a Heap



    8. Suppose new values are added to the last heap above (with 10 elements, the root is 7 that has both children with the value 12).

      1. If a new value of 20 is added what value is the parent of the 20 node?

      2. After adding 20, add the value 10. What are the values of 10's parent, and child(ren)?

      3. Give an example of one value that could be added to the heap that would end up at the root. Draw the resulting heap.


    9. Draw the heap that results from adding 12, 7, 11, 9, 15, 10, 8 in that order to an initially empty heap.


    10. What is the big-Oh complexity of finding the smallest element in a min-heap heap? And, what is the big-Oh complexity of finding the largest element in a min-heap? Justify your answers.