# Is it possible to find the nodes larger than k in a min-max heap in O(m) time?

Is it possible to find the nodes larger than $k$ in a min-max heap in $O(m)$ time, where $m$ is the number of nodes larger than $k$?

If it is possible, then how do I implement the rest of the standard heap procedures in standard time (insert and delete, extract min and extract max is easy obviously)?

If needed the whole problem statement goes like this:

We want to add operation to our (max) priority queue. We are interested in adding the following operation. Below, x and y are objects and x.key and y.key are their keys in the priority queue (the objects can also have other satellite data). If an implementation of the priority queue is done as in CLRS, chapter 6, then the table can be a table of objects – not numbers; in that case x and y can have an attribute i, so that x.i and y.i denote their places (indices) in the table.

• REMOVELARGEST(m): remove the m largest elements in the heap
• DELETE(x): remove the element x from the heap.
• FUSION(x,y): remove x and y from the heap and add the element z with key x.key+y.key
• EXTRACTMIN: remove and return the element with the smallest key

1. Expand the priority queue to support REMOVELARGEST(m) in $O(m*log(n))$ time.
2. Expand the priority queue to support DELETE and FUSION in $O(log(n))$ time
3. Expand the priority queue to support FINDLARGEST(k) in $O(m)$ time, where $m$ is the number of elements $>=k$.
4. Expand the priority queue to support EXTRACTMIN in $O(log(n))$ time.
• You've been asking a lot of questions about the same problem lately. Don't forget we won't be available during your final exams. Feb 11 '18 at 22:03
• Please credit the source of all copied material. See cs.stackexchange.com/help/referencing
– D.W.
Feb 12 '18 at 16:47