(a) Suppose you are given a (min)-heap containing n integers, and an integer z. Show that any algorithm to check if z is in the heap runs in (n) time. (b) Suppose we have a balanced binary tree but instead of the heap property, we have the following condition: For any node i, every node in i 's left subtree is less than or equal to the value of i, and every node in i 's right subtree is greater than or equal to the value of i. Show that given an integer z, we can check if z is in the data structure in O(logn) time. c) The data structure in part (b) implements a binary search tree. Unlike heaps, they are not implemented as arrays. Here we investigate why. Let's assume that we do represent a balanced binary search tree as we do a heap: the root is stored in position 1 , and a node i 's children are stored at index 2i and 2i+1. Argue that any procedure to insert a new element into a heap runs in (n) in the worst case. Here are, a few hints to get you started: - Here, "in the worst case" means that once you define the procedure and are given a binary search tree stored in an array, an adversary gets to choose a value to insert. There is some value the adversary can choose that will take (n) time to insert. - When we insert into a heap, how many "swaps" might we have to make, in the worst case? Why is this? And does the same structure hold for a balanced binary search tree? - Consider a set of numbers arranged as a heap vs. the same set arranged as a balanced binarysearch tree. Is there more than one "correct" data structure in either case