We assume the input for the problems contains distinct numbers.
1. Given an array A, build a heap out of it efficiently.

2. Given k sorted arrays of length n each, describe an algorithm that merges them efficiently.
3. Given an array A where each number is at most k spots away from its spot in the sorted array, describe an efficient algorithm that returns the sorted array.

2. Given k sorted arrays of length n each. Describe an algorithm that merges them efficiently.
3. Given an array A where each number is at most k spots away from it's spot in the sorted array, describe an efficient algorithm that returns the sorted array.

4. Given an array of n numbers, describe an efficient algorithm that prints out the smallest k numbers in the array.
5. A Young Tableau is a matrix where elements on each row or column appear in increasing order. Given a Young Tableau A, describe an efficient algorithm that returns the kth element of A.
6. Given a min heap A, give an efficient algorithm that outputs its kth smallest element.

7. Print out the first k numbers of the type 2^i^ * 3^j^.
8. Build a data structure where you can do insert(x) in O(log n), findMedian() in O(1) and deleteMedian() in O(log n).
9. Given A and B sorted arrays of length n, find out the k smallest numbers of the form A[i] + B[j].
10. Given a min heap of size n and a number X, give an efficient algorithm that tests if the kth smallest element in the heap is smaller than X.

7. Print out the first k numbers of the type 2^i^ * 3^j^.

protected

private