1. Suppose we used the zero element of our arrays, rather than ignoring it or using it to hold heapsize. Give new Parent, Left and Right functions that would work in case we were using A[0] as the root element of the heap. [But we are not using this zero element in everything below,except perhaps to hold heapsize.]

   0-based heaps: Parent( i ) = floor( (i - 1) / 2 ) Left( i ) = 2 * i + 1 Right( i ) = 2 * i + 2

2. Text, Exercise 6.1-4 on page 154. [Where in a max-heap might the smallest element reside, assuming that all elements are distinct?] [(Copying Strautman's answer) The smallest element would reside in one of the leaf nodes, since the max heap property specifies that A[Parent(i)] >= A[i] (or strictly > with distinct elements). If a node had any children, it could not be the smallest element.]

3. Text, Exercise 6.1-5 on page 154. [Is an array that is in sorted order always a min-heap?] Also is an array that is in reverse sorted order (elements non-increasing) always a max-heap? [(Ditto) Yes and yes. For a min heap, we must have A[Parent(i)] <= A[i]. For an array in sorted order, the children of any node at index k, if they exist, are at 2*k and/or 2*k + 1. Since the array is in sorted order and they are at a greater index, both children are greater than or equal to the parent, satisfying the min heap property. For an array in reverse-sorted order, the max heap property is similarly satisfied. Since for each parent node, the children are at a greater index than the parent, when the elements are non-increasing, we always have A[Parent(i)] >= A[i], the max heap property.]

4. Text, Exercise 6.1-6 on page 154. [Is the array with values {23,17,14,6,13,10,1,5,7,12} a max-heap? If not, why not? Note that these numbers are in array locations A[1], A[2], ... A[10].] [Heap property fails at item A[4] = 6. Need to swap A[4] and A[9] = 7 to restore heap property.]

5. Text, Exercise 6.2-1 on page 156. [Illustrate the operation of Max-Heapify(A,3) on the array A = {27,17,3,16,13,10,1,5,7,12,4,8,9,0}.] Is the result a max-heap? If not, why not? [after 1st interchange: heapsize:14, heap: 27, 17, 10, 16, 13, 3, 1, 5, 7, 12, 4, 8, 9, 0
    after 2nd interchange: heapsize:14, heap: 27, 17, 10, 16, 13, 9, 1, 5, 7, 12, 4, 8, 3, 0
   Yes, this is now a max-heap.]

6. Text, Exercise 6.2-3 on page 156. [What is the result of calling Max-Heapify(A,i) when the element A[i] is larger than its children?] [(Ditto) Calling Max-Heapify(A,i) when A[i] is larger than its children causes no change in the array. (We will have largest == i, so then no exchanges will occur and Max-Heapify will not be called again.)]

7. Text, Exercise 6.2-4 on page 156. [What is the effect of calling Max-Heapify(A,i) for i > A.heap-size / 2 ?] [(Copying Li's answer) Whenever i > A.heapsize/2, the node is a leaf. Therefore, the heap stays the same.]

8. Text, Exercise 6.2-5 on page 156. [Rewrite the code for Max-Heapify so that it uses an iterative control structure (a loop) instead of recursion. This is an example of removing tail-recursion.] Hint: It's mostly just a matter of giving the second parameter a new value while you go around a loop again.[Using exactly your text's algorithm from page 154, here is a simple answer:

   MaxHeapify2(A, i) { while(true) { l = Left(i); r = Right(i); if (l <= A.heapsize && A[l] > A[i]) largest = l; else largest = i; if (r <= A.heapsize && A[r] > A[largest]) largest = r; if (largest == i) return; exchange(A, i, largest); i = largest; } }

9. Suppose numbers {26, 5, 77, 1, 85, 11, 59, 15, 48, 19} are stored in array locations A[1], ..., A[10].
   1. Build A into a max-heap using the algorithm Build-Max-Heap from the text [page 157]. Notice that this starts by calling Max-Heapify(A,5) from the text [page 154]. Then proceed down from 5 to 4 to 3 to 2 to 1. [Final result is: {85,48,77,26,19,11,59,15,1,5}.]

   2. Show that the algorithm works in the case above if you start with 6 instead of 5 and work your way to 1. (This is trivial.) [If you start with 6, nothing different happens because, inside maxHeapify, the variables l and r will be greater than heapsize.]

   3. Text, Exercise 6.3-2 on page 159. [Show that the algorithm fails in the case above if you start at 1 and proceed from 1 to 2, 3, 4, to 5.] [Going from 1 to 5 in that order almost immediately results in A[1] = 77, A[2] = 85, which is not a heap.]

10. What property does the magic node floor(A.length/2) have? (Notice that in Java, since we have a zero element also, this would be floor((A.length - 1)/2).) [This gives the node with largest index that has children, that is, the largest index of a node with one or two children. The node at the next index value has no children (is a leaf node). This is where the function BuildMaxHeap starts out, and then works down to the root node.]

11. Text, Exercise 6.4-1 on page 160. [Illustrate the operation of heapsort on the array A = {5,13,2,25,7,17,20,8,4}. (Here again, A[1] = 5.)]
    [Here are the steps involved:

    after buildMaxHeap: heapsize:8, heap: 25, 17, 20, 7, 2, 13, 8, 4, heapsort,after step 8:heapsize:7, heap: 20, 17, 13, 7, 2, 4, 8, 25, heapsort,after step 7:heapsize:6, heap: 17, 8, 13, 7, 2, 4, 20, 25, heapsort,after step 6:heapsize:5, heap: 13, 8, 4, 7, 2, 17, 20, 25, heapsort,after step 5:heapsize:4, heap: 8, 7, 4, 2, 13, 17, 20, 25, heapsort,after step 4:heapsize:3, heap: 7, 2, 4, 8, 13, 17, 20, 25, heapsort,after step 3:heapsize:2, heap: 4, 2, 7, 8, 13, 17, 20, 25, heapsort,after step 2:heapsize:1, heap: 2, 4, 7, 8, 13, 17, 20, 25, heapsize:1, heap: 2, 4, 7, 8, 13, 17, 20, 25,

1. Text, Exercise 6.5-1 on page 164. [Illustrate the operation of Heap-Extract-Max on the heap A = {15,13,9,5,12,8,7,4,0,6,2,1}.]
   [Here are the successive steps:]

   main: heapsize:12, heap: 15 13 9 5 12 8 7 4 0 6 2 1 maxHeapify: heapsize:11, heap: 1 13 9 5 12 8 7 4 0 6 2 maxHeapify: heapsize:11, heap: 13 1 9 5 12 8 7 4 0 6 2 maxHeapify: heapsize:11, heap: 13 12 9 5 1 8 7 4 0 6 2 maxHeapify: heapsize:11, heap: 13 12 9 5 6 8 7 4 0 1 2 Max of heap: 15 main: heapsize:11, heap: 13 12 9 5 6 8 7 4 0 1 2

2. Text, Exercise 6.5-2 on page 165. [Illustrate the operation of Max-Heap-Insert(A, 10) on the heap A = {15,13,9,5,12,8,7,4,0,6,2,1}.]
   [Here are the successive steps:]

   main: heapsize:12, heap: 15 13 9 5 12 8 7 4 0 6 2 1 maxHeapInsert: heapsize:12, heap: 15 13 9 5 12 8 7 4 0 6 2 1 heapIncreaseKey: heapsize:13, heap: 15 13 9 5 12 8 7 4 0 6 2 1 -2000000000 heapIncreaseKey: heapsize:13, heap: 15 13 9 5 12 8 7 4 0 6 2 1 10 heapIncreaseKey: heapsize:13, heap: 15 13 9 5 12 10 7 4 0 6 2 1 8 heapIncreaseKey: heapsize:13, heap: 15 13 10 5 12 9 7 4 0 6 2 1 8 main: heapsize:13, heap: 15 13 10 5 12 9 7 4 0 6 2 1 8

   [Here is the program used for the two questions above (although it was assumed but not required that you would do these questions by hand):]

   // PQueueInt.java: priority queue of integers public class PQueueInt { private int[] A; private int heapsize; public PQueueInt(int[] Ap, int hs) { A = Ap; heapsize = hs; } public int qSize() { return heapsize; } public int heapMaximum() { if (heapsize < 1) { System.out.println("Empty Queue"); System.exit(0); } return A[1]; } public int heapExtractMax() { if (heapsize < 1) { System.out.println("Heap Underflow"); System.exit(0); } int max = A[1]; A[1] = A[heapsize]; heapsize--; maxHeapify(1); return max; } private int parent(int i) {return i/2;} private int left (int i) {return 2*i;} private int right (int i) {return 2*i + 1;} private void exchange(int i, int largest) { int temp = A[i]; A[i] = A[largest]; A[largest] = temp; } private void maxHeapify(int i) { printheap("maxHeapify"); int l = left(i); int r = right(i); int largest; if (l <= heapsize && A[l] > A[i]) largest = l; else largest = i; if (r <= heapsize && A[r] > A[largest]) largest = r; if (largest != i) { exchange(i, largest); maxHeapify(largest); } }

   public void maxHeapInsert(int key) { if (heapsize >= A.length - 1) { System.out.println("Heap Overflow"); System.exit(1); } printheap("maxHeapInsert"); heapsize++; A[heapsize] = -2000000000; heapIncreaseKey(heapsize, key); } void heapIncreaseKey(int i, int key) { if (key < A[i]) { System.out.println("New key < Current"); System.exit(2); } printheap("heapIncreaseKey"); A[i] = key; printheap("heapIncreaseKey"); while (i > 1 && A[parent(i)] < A[i]) { exchange(i, parent(i)); i = parent(i); printheap("heapIncreaseKey"); } } public void printheap(String id) { System.out.print(id + ": heapsize:" + heapsize + ", heap: "); for (int i = 1; i <= heapsize; i++) { System.out.print(A[i] + " "); } System.out.println(); } public static void main(String[] args) { int[] A = {0,15,13,9,5,12,8,7,4,0,6,2,1,-1,-1,-1}; int heapsize = 12; PQueueInt pq = new PQueueInt(A, heapsize); pq.printheap("main"); // do one of the other of the two below: System.out.println("Max of heap: " + pq.heapExtractMax()); // Problem 2 // pq.maxHeapInsert(10); // Problem 3 pq.printheap("main"); } }

3. Text, Exercise 6.5-4 on page 165. [Why do we bother setting the key of the inserted node to -∞ in line 2 of Max-Heap-Insert when the next thing we do is increase its key to the desired value?] (This "cheating" question doesn't have a very satisfactory answer, as far as I know. But hey, maybe you'll come up with a good answer.)
   [When I first assigned this problem I thought there was a simple answer. In the use on page 163, the location of A[A.heapsize] could be given any value at all or left undefined and the Heap-Increase-Key would still work as long as the check and error message was left off. The Heap-Increase-Key algorithm works for any node i, but for non-leaf nodes the check and error message is required. If you want to keep the Heap-Increase-Key as it is in its general form, then you need to set A[A.heapsize] = -∞ to guarantee that the result is a heap and that the general algorithm will work. Kind of a lame reason.]

1. Implement heapsort in Java or C. You must use the algorithms as given in the text and on our web pages. Make the code as simple as possible. This includes storing the heapsize in the element A[0].

2. As a use for your implementation, add code to count the number of interchanges during the sort. Using an array of size n, create an array in sorted order (just insert i into A[i]) and count in this case. Similarly, use an array in reverse sorted order (just insert n-i+1 into A[i]). Finally try an array with random data. Use something like n=1000, or n=10000 for a run. [If you use an "exchange" function for interchanges, it is easier to do the count.] [My program and data for this is: Heap Sort, Recorded Exchanges.]

3. In all of my runs to solve ( ii ) above, my program shows reverse sorted order requiring the fewest interchanges of the three possibilities above. Can you think of a reason for this? [In this case the initial array is already a max heap, so the first step of heapsort (BuildMaxHeap) is trivial.]

C(n,k) = 1, if k = 0, or if n = k
C(n,k) = C(n-1, k) + C(n-1, k-1), otherwise

One requires that n >= 0, k >= 0, and n >= k. As with the Fibonacci program, for sample inputs n and k, you should print the number of calls with and without memoization, and in case of memoization, the number of table inserts. Try several runs, including at least the pairs: <n,k> = <4,0>, <4,1>, <5,4>, <6,4>, <7,3>, <15,10>, <20,10>, <30,15>, <35,10>, <35,12>. [Hint: Note that you will need a 2-dimensional array for the "memos", the answers.] [Here's my program for this: Memoized Calculation of Combinations.]

(Of course there is another, completely different formula for C(n,k), one you are likely more familiar with, namely:

                            n!
           C(n,k) =   -------------
                       k! * (n-k)!

Thus C(7,3) = 7!/(3!*4!) = 7*6*5/(3*2*1) = 35.)

[C(n,k) is called the combinations of n things taken k at a time. It is also called the binomial coefficient, since it is the kth coefficient of (x + y)ⁿ. C(n,k) is also commonly denoted by putting n over k (no line between) and enclosing in parentheses.]