Homework #5

- Below is a list of integers. Please determine, without transforming
the list into an actual tree, whether it represents a HEAP.
While keeping the list in list form, implement the heapsort procedure
on it and show the intermediary partially ordered lists generated by
the algorithm until a fully ordered list is achieved.
64,42,39,31,20,30,40,19,33,50

- Provide an algorithm, based on the heapsort algorithm, for finding the number second to the biggest, in a given list of keys. How many comparisons does your algorithm require in the worst case?
- Provide an algorithm that rearranges all the numbers, in a given list of positive and negative integers, so that all the negative integers precede all the positive ones , using the minimum possible number of exchanges (the list need not be sorted, just separate between positive and negative numbers).
- We are given two SORTED lists of n keys each. We want to find the median of the 2n keys. One possible way to do it is to merge the 2 lists into an ordered 2n list and find the median directly. How many comparisons does this method require. Can you think of another method which is O(logn)? Hint: Recal that a key cannot be the median if it is bigger or smaller than n+1 elements and take a clue from binary search.