Homework 2 Clarifications

Updated 1-12-2014

• 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 edge and unallowed or illegal cases.

In addition to directly manipulating the array of values and knowing the size of the heap, if you want to make use of them in your solution, your pseudo code can make use of the following 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.

Keep in mind that your answers to 2a and 2c should return the heap to its original state if you modify it using one of these routines. You are NOT required to use all or even any of these routines in your solution - we just want you to use these versions if you do.

Notes: 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.

• Problem 2, part c

In thinking about the run time of this algorithm, consider both the total number of items $n$ in the heap, as well as the number of elements that are less than the value being tested for. If their are only a small number of elements identified as less than the search value, your algorithm should identify them without testing all values in the array.