CSCI 3300
Spring 2009
Exercises for Quiz 13

1. If you insert 6 into the following min-heap, then reorder to restore the heap order, what heap do you get?

   

   Answer

2. If you remove the smallest value from the following min-heap, then reorder to restore the heap order, what heap do you get?

   

   Answer

3. If you insert 10 into the following min-heap, then reorder to restore the heap order, what heap do you get?

   

   Answer

4. If you remove the smallest value from the following min-heap, then reorder to restore the heap order, what heap do you get?

   

   Answer

5. Suppose that a min-heap is stored in an array. If you reverse the contents of the array, does it necessarily satisfy the ordering requirement for a max-heap? Why or why not?

   Answer

6. Type Node is shown at the bottom of the page. It is used as the node type for binary search trees.

   Assume that function insert(x,t) is available to you, where insert(x,t) inserts x into binary search tree t, modifying t.

   Write a definition of function insertAll(s,t), which takes two binary search trees s and t and inserts all members of tree s into tree t.

   Answer

7. To within a constant factor, how long does Heapsort take to sort an array of n numbers, in the worst case?

   Answer

struct Node
{
  int item;
  Node* left;
  Node* right;
  Node(int i, Node* L, Node* R)
  {
    item = i;
    left = L;
    right = R;
  }
};