Short Answers 1. Suppose that we want to create a heap where each node contains information of some data type called Item (which has a default constructor and a correct value semantics). What additional factor is Short Answers 2. A heap is a binary tree where the entries can be compared using the usual six comparison operations (that form a total order semantics). Write the two rules that the binary tree must follow in order 3. Give two different reasons to explain why the following binary tree is not a heap: required for the Item data type? Section 11.1 Heaps for the structure to actually be a heap 73 46 68 81 11 4. Draw a new heap that is created by inserting 82 into the following heap: 910 73 68 1 3 11 5. Draw a new heap that is created by removing one item from the following heap: 910 68 6. Suppose that you are performing a reheapification downward. Write a precise condition that describes the situation that causes the reheapification to stop 7. Suppose that you are performing a reheapification upward. Write a precise condition that describes the situation that causes the reheapification to stop 8. Suppose that a non-leaf node in a B-tree contains 42 entries. How many children does the node have? 9. Draw an example of a B-tree with four nodes and seven integer entries. The value of MINIMUM is 1 for this tree 10. Draw a new B-tree that is created by inserting 82 into the following B-tree. For this example, the minimum number of items in each node is 1. Note that the rightmost leaf starts with two entries, 71 and 93. Short Answers Section 11.2 B-Trees S6 2 8 63 71 and 93