Homework 5

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.

     

  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.
    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.

     

  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.
    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.

     

  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.
    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.