I have the following problem:
Given an unsorted array A of size n, print the first k elements in A larger than its median.
Here's my approach to the problem:
1. Create a minHeap and a maxHeap 2. Iterate over elements in A // O(n) - if maxHeap.count < minHeap.count insert current element to maxHeap // O(log(n)) else: insert current element to minHeap // O(log(n)) 3. if maxHeap.count < minHeap.count: median = minHeap.extractMin() 4. output k elements from minHeap // O(klog(n))
This maintains a maxHeap of elements less than the median and a minHeap of elements greater than or equal to the median. But from my analysis, this seems to take
O(nlogn + k(log(n)) which is no better than sorting A first and grabbing A[n/2:n/2+k] in just
O(nlog(n) + k).
Now I have 2 questions:
- Is my analysis tight? I am doubtful since the heaps have at most i elements in the ith iteration, not n.
- Is there a better algorithm? Maybe something like O(n+klog(k))?