Homework 2 Clarifications

Updated 1-21-2015

• For problems 1 and 2 we are looking worst case running time of the two algorithms.

Updated 1-20-2015

• For problems 1 and 2 you may assume that you are just dealing with a heap of integers.

Updated 1-18-2015

• Problems 1 & 2

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 1 and 2 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.