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





Expand the priority queue to support REMOVELARGEST(m) in $ O(m*log(n)) $ time.
Expand the priority queue to support DELETE and FUSION in $ O(log(n))  $ time
Expand the priority queue to support FINDLARGEST(k) in $ O(m) $ time, where $ m $ is the number of elements $ &gt;=k $.
Expand the priority queue to support EXTRACTMIN in $ O(log(n)) $ time.
You can use a max-heap and a min-heap containing the same elements, with pointers joining pairs of identical elements in both heaps. This allows supporting all the usual operations in logarithmic time, and the new operation (finding all nodes larger or smaller than a given value) in time linear in the output size.