I have a list of integer pairs. The value of this list is the sum of the maximum values of each pair.

For 

> (0, 5) (20, 5) (6, 8)

 the value would be 

> 5 + 20 + 8 = 33



Given a list like this, I need to maximize its value. The only operation I can do is swap an element of a pair with another element of a different pair. 
For the example above I can do this

> (**6**, 8) <> (0, **5**)

The list would become

> (0, 6) (20, 5) (5, 8) => value = 6 + 20 + 8 = 34

So in order to increase the value I'd need to find 2 pairs `(a,b) (c,d)` with `min(a,b) > max(c,d)` and then swap `min(a,b)` with `max(c,d)`, right ? If no such pairs exist then the we cannot increase the value of the list.

Solution:
I need to keep the pairs sorted in descending order by the minimum value and in ascending order by the maximum value because I need to compare the pair with the greatest minimum to the one with smallest maximum.

I thought about using 2 heaps for this, a minheap which orders by maximums and a maxheap which orders by minimums. This way, each time I need to compare I can just compare the roots of the two heaps.

The problem is that I also need to update these values, by exchanging the minimum value of 1 pair with the maximum value of another pair and then reorder the heaps so I would need to also keep additional information for each heap node for the position in the other heap. Something like [this][1].

Is this the best way to approach this problem, or are there better data structures that I can use ?


  [1]: https://en.wikipedia.org/wiki/Double-ended_priority_queue#/media/File:Dual_heap.jpg