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))?
2.
guarantee the upper half of elements to end up inminHeap
? Consider k = 2, A = 6 4 2 1 3 5 7. (Actually using both heaps sound promising, but you'd need to keep max(maxHeap) no greater than mix(minHeap) - and repeated values mess up things about as good as with other approaches.) $\endgroup$