Homework 5 Solution

CS409 - Spring 2000

Due: Thursday, Mar 2

  1. (10 pts) Given the following min-heap implemented using an array: 
    				 (2)
				/   \
			    (13)     (7)
			   /   \     /  \
		       (17)   (14) (22)  (8)
		      /
		  (21)
    1. Show what the heap looks like after deleting the minimum element.
    2. Show what the heap looks like after inserting 15 into the original heap.
      after deleting min after inserting 13 
            7
    /   \
  13     8
  /\     /\
17  14 22  21
      		 
               2
       /   \
     13     7
    / \    / \
  15  14  22  8
 / \
20 17

     

  2. (10 pts) Given a set of n numbers stored in an array, we wish to find the k smallest numbers of this set and report them in sorted order.  One possible method is to build a Priority Queue using all the numbers (we haven't talked about it in class, but this can be done on O(n) worst-case time) and then call getMin() k times.  This method takes worst-case time O(n + k log n).  Analyze each of the following methods to determine their running time in terms of n and k.  
    1. Sort all the numbers then report the k smallest.
      It takes O(n log n) time to do the sorting.  Once the sorting is done it takes O(k) time to report the k smallest numbers.  Total time is O(k + n log n).
    2. Use a Priority Queue of size at most k.  Explain how this can be used to solve the problem efficiently and determine the running time.
      The idea here is to use a max-heap of size k; this heap stores the smallest k numbers that we've seen so far.  We use a max-heap because this makes it easy to decide if a new number is better than the worst number that we're holding in the heap.  If a new number is smaller than the root of the heap then we perform a getMax on the heap to get rid of its root and then we insert the new number.  Each heap operation takes time O(log k) and we have to do at most O(n) heap operations.  At the end we need to report the k smallest values that are stored in the heap; this takes O(k) time.  Thus, total time is O(k + n log k).

     

  3. (10 pts) For a heap (implemented using an array):
    1. Do we always get back the same heap if we perform getMin() and then re-Insert the same item?  Either argue that the heap must remain the same or give a counterexample.
      The heap is not necessarily the same.  Here's an example:
      initial heap after getMin() after insert(1) 
         1
  / \
 2   3
      		 
         2
  /
 3
      		 
         1
  / \
 3   2
    2. How about if we Insert a new item that happens to be the smallest and then we immediately Delete it?  Either argue that the heap must remain the same or give a counterexample.
      In this case, the answer depends on whether items are allowed to have equal priorities.  In particular, when doing the "bubble-down" operation, we need to decide which of the two children to promote in the case where the two children have equal priorities.  Suppose we decide to promote the left child in this case.  Here's an example in which this causes the tree to change:
      initial heap after insert(1) after getMin() 
           2
   /   \
  2     3
 / \ 
4   5
      		 
           1
   /   \
  2     2
 / \   /
4   5 3
      		 
           2
   /   \
  3     2
 / \ 
4   5

      A similar example could be found if we make the choice to always promote the right child.

      If all priorities are guaranteed to be distinct then the heap does remain the same.  To see this, consider the path, from leaf to root, that the smallest item (call it x) follows when it is inserted.  Each item along this path is moved one "downward" as x is moved into its correct position at the root.  If x is then deleted, the last item along this path is moved into the root position; this item is then "bubbled down" the tree until it reaches the correct position.  This has the effect of moving each item along the path "upward" by one level.  This returns the tree to its original configuration.

     

  4. (10 pts) For a BST (without balancing):
    1. If we Insert an item and then immediately Delete it do we always get back the same BST?  Either argue that the BST must remain the same or give a counterexample.
      In this case, we do get back the same BST.  When the item is inserted, it appears as a leaf.  Deleting a leaf-node causes no other changes to the tree.
    2. If we Delete an item and then immediately re-Insert it do we always get back the same BST?  Either argue that the BST must remain the same or give a counterexample.
      In this case, the resulting tree is not necessarily the same as the original tree.  Here's a really small example:
      initial BST after delete(A) after insert(A) 
      A
 \
  B
      		 
           B
      		 
        B
 /
A