*DataStructures and Algoritm (C Programming)
Your project leader has been quite impressed by your performance on binary search trees, and started entertaining the idea of keeping you full time after you graduate. However, she needs to make a case to her manager about how magnificent a problem solver you are. Thus, she decided to put a few more challenges for you. This time she wants to test how well versed you are with heaps. You are given an unsorted array of size n. Below are the set of questions that you need to solve to prove your worth by using this unsorted array.
(a) The naive way of generating a heap with that array is by using a separate list of the same size and generating the heap by inserting elements one by one. Give a O(n log n) time algorithm to generate the heap.
(b) That was easy. How about generating the heap in place? Give pseudocode or explain in plain English of a function, that generates a heap without using a second list. You can only use upheap/downheap functions that we used in class, while other functions (such as insert/deleteMin) are not allowed. What is the runtime of your algorithm?
(c) Although we stated that generating the heap would take O(n log n) above, it was actually a loose bound which assumes that each insertion will take O(log n) time, for each of the n insertions. However, as you might have noticed when going though your iterations in the previous part of the problem, fixing the heap property for some nodes (or with the similar idea, inserting elements to a heap in early stages) do not always take O(logn) where, n is the size of the final heap. In fact, earlier stages takes less time, revealing that our initial O(nlogn) time might have been a loose bound. Make a careful analysis of the make heap algorithm and show that it has O(n) time.