All Questions
Tagged with heaps selection-problem
3 questions
1
vote
1
answer
1k
views
How to find kth largest element in (max) priority queue in O(m) time?
Here is my exercise.
FINDLARGEST(k): return the elements in the heap with key >=k" ... "expand the priority queue (max-heap) so that it supports FINDLARGEST(k) in O(m) time, where m is the number ...
- 83
1
vote
1
answer
777
views
Given a binary min-heap, getting a sorted array of the $\log n$ smallest elements
Let's say we have a binary min-heap of size $n$, and we want to get an array of the smallest $\log n$ values in the heap, sorted. What is the best complexity that we can get and how do we implement it?...
- 563
1
vote
0
answers
224
views
Who first invented and analysed algorithm of finding median in a stream of integers using two heaps?
There is popular problem:
Given that integers are read from a data stream, find the median of
elements read so far in an efficient way.
One of possible solutions:
Use max-heap for left heap (i....
- 43