Homework 2 Clarifications

Updated 4-12-2013

• 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.

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. We want you to use the versions of the methods listed above in your answer to the problem.