CSE 373 Data Structures 10sp, Homework 4

Due at the BEGINNING of class, Friday, 5/07/10

1) AVL Trees: Show the result of inserting values in this order into an initially empty AVL tree in this order: 5, 10, 12, 14, 1, 15, 6, 3, 2, 9, 7, 4

2) Binary Min Heaps and 3-heaps: For all three questions draw BOTH a picture of the tree structure AND what the final array looks like. You do not need to show intermediate values of the array structure. Showing intermediate pictures of the tree structure is also not required but may allow some partial credit to be assigned. Please circle your final answer to all three questions.

a) Show the result of inserting the following values in this order into a binary min heap using insert: 11, 12, 2, 14, 6, 5, 8, 15, 3, 9, 7, 4, 10, 13, 1

b) Show the result of using Floyd’s buildheap method (as described in class and in the book on p. 212) to create a heap out of values assuming you are given them in an array laid out in this order: [11, 12, 2, 14, 6, 5, 8, 15, 3, 9, 7, 4, 10, 13, 1]

c) Show the result of inserting the following values in this order into a 3-heap using insert: 11, 12, 2, 14, 6, 5, 8, 15, 3, 9, 7, 4, 10, 13, 1

3) Binary Min Heap Algorithms: For both of these problems, for full credit your solution should be the most efficient possible – perhaps in the worst case they might need to examine every element in the heap, but in general this should not be the case. You may assume an array layout of the binary min heap as discussed in lecture and in the book. You also may assume that your algorithm has direct access to the heap array (it does not need to manipulate it just by using the standard heap operations – insert, deletemin, findmin, etc.). Your algorithm should not modify the heap (just like a findmin does not modify the heap) – or at the very least, if it does, it should put it back identical to how it was before you started. You may want to refer to the written hw guidelines for a reminder about proper pseudocode.

a) Give pseudo code for an efficient algorithm to find the maximum value in a binary min heap. What is the worst case big-O running time or your algorithm?

b) Give pseudo code for an efficient algorithm to find all nodes less than a given value in a binary min heap. Your algorithm should just print out the values it finds. What is the worst case big-O running time of your algorithm?

4) Skew Heaps: Show the result of inserting values in this order into an initially empty skew heap: (2, 1, 3, 6, 4, 5, 7, 8, 9, 10, 11)

5) Leftist Heaps:

Below are two leftist heaps. Show the result of merging them together using the algorithm we discussed in class. You are only required to show the final tree, although if you draw intermediate trees, please circle your final result for ANY credit.

6) Disjoint Sets: Consider the set of initially unrelated elements 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14.

a.) Draw the final forest of up-trees that results from the following sequence of operations using on union-by-size. Break ties in size by keeping the root of the set that the first argument belongs to as the new root. Use the Hw4Union given below that is able to take any element as a parameter, not necessarily the name of a set. It finds the set each element belongs to and then unions those two sets. Be sure to include all elements of the set in your final answer.

hw4Union(int x, int y) {
u = Find(x); // Find here is done without path compression.
v = Find(y);
Union(u,v); // Use Union-by-size
}

hw4Union(3,0), hw4Union(3,4), hw4Union(7,9), hw4Union (9,3), hw4Union (7, 14), hw4Union (6,8), hw4Union (11,5), hw4Union (8,5), hw4Union (6,4), hw4Union (1,12).

b.) Draw the array representation of your answer above. Use the value -1 to represent a root.

c.) Draw the new forest of up-trees that results from doing a Find(5) with path compression on your forest of up-trees from (a).