Heaps shortlist

Cosmin Negruseri
17 iunie 2015

Here are a few problems where you can play with the heap data structure. Feel free to discuss them in the comment section.

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 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ⁱ * 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.