1. Assume you're given an array with the following values stored in positions 0 through 9:
    -100 10 50 20 70 60 30 80 100 90
    (a) Draw the heap corresponding to this array (remember that the 0th position represents a sentinel value).
    (b) Show the heap after Insert(40) is called.
    (c) Show the heap from part (b) after DeleteMin() is called.
    (d) Show the heap from part (c) after DecreaseKey() is called on the node with value 100 to lower it to 35.
    (e) Show the heap from part (d) after IncreaseKey() is called on the node with value 20 to raise it to 85.

  2. Write a function...

    (a) BinTreeIsHeap(Tree T) that returns whether or not a binary tree of integers meets the heap ordering criteria (C++ folks should make this a method of the Tree class...). You should assume that the tree structure is the same as in Assignment 3, problem 3, and that you will need to refer to the internal structure. You may also assume that the tree is complete, so you don't need to check that it has the correct shape.

    (b) ArrayIsHeap(int *arr,int size) that returns whether or not an array is a legal heap (size indicates the number of elements in the array). You may assume that the array starts at position 1 rather than 0.

  3. The Computer Science Department assigns grad student desks based primarily on seniority. Thus, when a new desk becomes available, a 3rd year student has priority over 1st and 2nd year students. For students within the same year, a student already in the office with the free desk has priority over one outside the office. Students with equal priority are handled on a first-come, first-serve basis. Assume that whenever a desk becomes available, we create a heap to store all of the requests for that desk that we get.
    (a) Describe a scheme that assigns numeric priorities to students' requests in accordance with the department policy.
    (b) Would your priority scheme use a minheap or a maxheap?