Objectives: Understanding heaps and hashing
Problem 1: Max Heap [10 Points]
Given a max heap (implemented with an array) where might the smallest element be stored? Explain why. How long would it take you to find it?
Problem 2: Hashing [20 points, 5 for each part]
Given input {4371,1323,6173,4199,4344,9679,1989} and a hash function h(x) = x mod 10 show the resulting:
a. Separate chaining hash table
b. Hash table using linear probing (f(i) = i, using notation from class and the book)
c. Hash table using quadratic probing (f(i) = i^2)
d. Hash table with second hash function h2(x) = 7 - (x mod 7)
Problem 3: Determining a Heap [15 Points]
A tree can be printed by using the following code:
print("Tree: ");
preorder (root);
where the preorder function is defined as follows:
preorder (node t)
{
if (t == null)
return;
print ("[ ");
print (t.element + " ");
preorder(t.left)
preorder (t.right);
print ("] ");
}
Sample output:
Tree: [ 36 [ 14 ] [ 21 [ 19 ] ] ]
Tree: [ 24 [ 20 ] [ 17 ] ]
Tree: [ 36 [ 24 [ 21 [ 19 ] [ 17 ] ] [ 20 ] ] [ 14 ] ]
Notice that because of the brackets ' [ ' and ' ] ' the strings above uniquely define the shape and stored elements.
Write in pseudo-code a boolean function isHeap(char[] str) which takes an array of letters and brackets ' [ ' and ' ] ' (output by the preorder function) and determines if the tree represented by str obeys the heap-order property.
For example, the string “[ Y [ M ] [ S [ R ] ] ]” obeys the heap-order property (as well as the 3 strings in sample output), but the string
“[ Y [ M ] [ B [ R ] ] ] ” does not – Here we assume a max heap i.e. Z is the maximum element and A is the smallest, you may assume uppercase letters. You may assume that your input is a valid binary tree, you just need to check the heap-order property.
HINT: Your function needs to pass through the string only once, for each node check whether its value is smaller than that of the parent. Use a stack to keep track of the parent of the node being considered, use the parentheses as your guide.
Problem 4: Merging leftist heaps[10 points]
Verify (give an argument) that the merge routine discussed in class returns a leftist tree.
HINT: You need to show that the new tree has the leftist property and the heap order property. Showing the heap order property is easy, think about the rule for the recursive merge. To show the leftist property, notice that the trees returned when the recursion bottoms out are leftist, and argue that this property is maintained in each tree returned by the merge function.