Homework 4
Due Dates:
 Sections 1 & 3: Thursday, October 24, in class.
 Sections 2 & 4: Monday, October 28, in class.
Referenced exercises are from Data Structures and Algorithm Analysis in Java by Mark A. Weiss.

Exercise 6.2: [Weiss, 3/e]
 Show the result of inserting 10, 12, 1, 14, 6, 5, 8, 15, 3, 9, 7, 4, 11, 13, and 2, one at a time into an initially empty binary heap.
 Show the result of using the lineartime algorithm to build a binary heap using the same input.

Exercise 6.8: [Weiss, 3/e]
Show the following regarding the maximum item in a minheap with N items. (Note: A minheap is a heap with smaller values stored closer to the root.)
 It must be at one of the leaves.
 There are exactly ^{⌈} N/2 ^{⌉} leaves. (Here ^{⌈} N/2 ^{⌉} is the ceiling of N/2.)
 Every leaf must be examined to find it.

Exercise 6.18: [Weiss, 3/e]
A minmax heap is a data structure that supports both deleteMin and deleteMax in O( log N ) time per operation. The structure is identical to a binary heap, but the heaporder property is that for any node X:
 at even depth:
 the element stored at X is smaller than or equal to the parent but larger than or equal to the grandparent
 at odd depth:
 the element stored at X is larger than or equal to the parent but smaller than or equal to the grandparent
See Figure 1 below.

How do we find the minimum and maximum elements?

Show what happens to the minmax heap in Figure 1 after inserting 29, 4, 90, 5, 41, 9, 93 and 67. Show your work, then draw a clean copy of the final minmax heap.
Hint: in a minmax heap, each element is in the interval between its parent and its grandparent. For example, 20 is between 17 and 80; 13 is between 12 and 52; 42 is between 28 and 87. At even and odd levels, the parent and grandparent swap places as the left or right endpoint of the interval.
Another way to think about minmax heaps is that the even levels form a minheap where a node's key is smaller than those stored in its grandchildren (up to 4 of them); and the odd levels form a maxheap where a node's key is larger than those stored in its grandchildren. (Note: not all minheaps and maxheaps interlaced this way make a minmax heap, since interlacing does not guarantee the interval condition.)
When you insert an item into a minmax heap, you add the new item at the last level, just like in a regular binary heap. However, you have to decide whether the item should percolate up the minheap through the even levels or percolate up the maxheap through the odd levels. This is determined by comparing the new item with its parent.

Show what happens to the minmax heap in Figure 1 after two deletemin operations. Also, show what happens to the minmax heap in Figure 2 after one deletemin operation. Finally, show what happens to the minmax heap in Figure 3 after one deletemin operation. Double check your answer and make sure that the interval condition is maintained at every node.
Hint: deletemin for minmax heaps start out very much like deletemin in binary heaps. The root is replaced by the last item in the heap. This new item must then trickle down through the even levels of the min heap until it reaches "bottom". At the bottom, however, the interval condition might be violated because the new item is too big. This item may have to percolate up the max heap through the odd levels. When the new item reaches "bottom", you may have to check its parent or its children to see if the interval condition holds (depending on whether the last level is even or odd).

Show what happens to the minmax heap in Figure 1 after two deletemax operations. Also, show what happens to the minmax heap in Figure 4 after one deletemax operation. Double check your answer and make sure that the interval condition is maintained at every node.
Hint: deletemax for minmax heaps is analogous to deletemin.
Fig. 1 [Fig. 6.57 from textbook]
Fig. 2
Fig. 3
Fig. 4