Is it possible to find the nodes larger than k in a min-max heap in O(m) 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.