Homework 2 Clarifications

Updated 1-23-2013

• Problem 1

You are welcome to show more intermediate trees or arrays than the numbers listed below if you like.

• a) We expect 11 trees and 1 array as your answer.
• b) We expect 1 tree and 1 array as your answer.
• c) We expect 2 trees and 1 array as your answer.
• Problem 2

a) When in doubt, feel free to make your pseudo code closer to Java. The pseudocode for deletemin and insert on the slides might be a good guide - they also demonstrate how your routines can expect to have direct access to the array and to know the size of the heap. Most students tend to leave out details that should be included. Many times if they had thought through all of these details they might have uncovered a problem with their solution. So think through the details! This includes handling unallowed or illegal cases.

I had a few questions about which versions of methods should be used. Your pseudo code can make use of these routines:

• insert(val) - inserts val into the heap
• val deletemin() - removes and returns smallest val in heap
• percolateUp(array_index) - moves the value in location array_index up in the heap if needed.
• percolateDown(array_index) - moves the value in location array_index down in the heap if needed.

Assume that all of these routines leave the heap as a proper heap when finished. The versions of percolateUp and percolateDown on the slides behave slightly differently in that they take two parameters (value and hole) and return an index where the value should be written - so the heap is not really finished until insert or deletemin, (who called them) finishes. If you have already answered the question using the specific methods from the book or lecture that is fine, just be sure to clarify what you are using.

b) Give your answer in big-O

• Problem 3

In case the general idea is not clear, d-Heaps are discussed in section 6.5 of Weiss.

You may find it useful to do part e before doing part d.