Introduction to Programming in Python, Aug-Dec 2014
                          Assignment 5
                  Due Saturday, 25 October, 2014

----------------------------------------------------------------------
Instructions

** IMPORTANT: Note new policy regarding naming of zip file **

1. For each question, write a separate Python program with the
   filename indicated in the question.

   Zip your solutions into a single archive.  Use your CMI
   username to name the zip file (e.g. "madhavan.zip") and submit
   the zip file via moodle.

   If you don't name your zip file or the enclosed Python file
   correctly, you risk losing marks.

2. If the question asks for a function, you *must* write a
   function in Python (i.e., def f(x): ... )  Ensure that the
   function you define has the name indicated in the question.
   Also ensure that your function returns the value asked for,
   rather than printing it.

   If you add code to your file to test your function, make sure
   you *remove* this code when you submit your solution.  The
   Python file you submit should have *only* the function
   definition.

----------------------------------------------------------------------

NOTE: This assignment contains only one problem, and requires you
      to write four functions in a single file.

Filename: heap.py

Write the following collection of Python functions that implement
max-heaps.  

Note: You should write all the functions using the concepts about
  heaps discussed in class.  Do not submit trivial solutions that
  use built in list functions to construct a heap by sorting the
  values in descending order.


   heapify(l) 

     Transform a list of integers l into a max-heap in place.
     (Use the O(n) bottom-up algorithm.)

   check_heap(h)

     Return True of list h is a max-heap, False otherwise.

   deletemax(h)

     Delete and return the maximum element from the heap h and update
     the heap accordingly (modify h in place).
               
     -- Raise an IndexError exception with a suitable message if the heap
        is empty.

     -- Raise a ValueError exception with a suitable message if the
        input list is not a heap.

   insert_heap(h,v) 

     Insert v into the heap h (modify h in place).

     -- Raise a ValueError exception with a suitable message if the
        input list is not a heap.

Look up the documentation for 'raise' for details about raising
exceptions.  For instance, see
http://www.cmi.ac.in/~madhavan/courses/python-2014/docs/python-3.2.1-docs-html/tutorial/errors.html

======================================================================