Question

Implement the function is_maxheap which takes a list of integers and returns True if the list represents a valid max-heap, and False otherwise. Assume that the list represents the contents of a complete binary tree, following the parent/child indexing conventions established in class. E.g., is_maxheap should return True for the following inputs: a) [] b) [10] c) [10, 7, 8] E.g., is_maxheap should return False for the following inputs: a) [1, 2] b) [5, 6, 3] You should not define or use any external data structures in your implementation besides the list passed in.

Answer 1

Answer:

I am writing a Python function:

def is_maxheap(list):

   #finds the length of the list  

   size=len(list)

   #loop has a variable i which starts traversing from root til end of last #internal node

   for i in range(int((size - 2) / 2) + 1):  

       if list[2 * i + 1] > list[i]:  #If left child is greater than its parent then return #false  

               return False  

       if (2 * i + 2 < size and

           list[2 * i + 2] > list[i]):    #checks if right child is greater, if yes then #returns false  

               return False

   return True

Explanation:

The function is_maxheap() traverses through all the internal nodes of the list iteratively. While traversing it checks if the  node is greater than its children or not. To check the working of this function you can write a main() function to check the working on a given list. The main() function has a list of integers. It then calls is_maxheap() method by passing that list to the function. The program displays a message: "valid max heap" if the list represents valid max-heap otherwise it returns invalid max heap.

def main():

   list = [10,7,8]  

   size = len(list)  

   if is_maxheap(list):

       print("Valid Max Heap")  

   else:  

       print("Invalid Max Heap")          

main()

The program along with its output is attached in a screenshot.