Data structure for sorting by multiple attributes

Question

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.

Edit: Just to clarify, I need to do this operation as many times as needed to obtain the maximum value, not just once.

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 two 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 Dual heap in Double-ended priority queue.

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

Answer 1

I think you may be thinking about it too hard, or trying to complicate it more than necessary.

When a pair is to be modified, remove it from both heaps, modify it, then add it to both heaps.

One little issue you might encounter is that once you have found in one heap a pair that you want to alter, how to locate that pair in the other heap. If pairs are unique, this is not an issue. If pairs are not unique, then you may need to add a field to uniquely identify them. Unless the language you are using already provides some kind of identity. (For example, in Java, you could compare by reference.)

Answer 2

Your problem can be broken down into two parts:

• a sorting algorithm that takes a value from a given element
• a method to choose which value to extract, given a feature name

So something like (python-like pseudocode):

data = new MyDataStructure()
#Insert some values into it..
#...

def extract_feature(myObject, feature_name):
   return myObject.getFeature(feature_name)


print sorted(data, (key=lambda x: extract_feature(x))

Re: your comment You are talking about datastructures, but what you are really after..is a sorting algorithm that can take an object type and change the a.compareTo(b) call on the fly. In other words, any datastructure will do. Your sorting algorithm just needs to know how to compute the key with which the sorting will be done.

Example: https://wiki.python.org/moin/HowTo/Sorting#Key_Functions

Answer 3

What you are really looking for is the sum of the highest 50% of the elements.

Given a set of n pairs, there are 2n elements. Let us split these elements into two sequences (not sets, elements can occur multiple times), s and t each containing n elements. We swap elements until it is true that for every element e in s and f in t, that e <= f.

Now you simply sum up the elements in t, giving us the result. This is very similar to sorting the elements in each pair, discarding the half of the elements that are smallest, and summing the rest.

The easy way to achieve these results is with the following algorithm:

1. Split each pair in n into two numbers and insert them into list t.
2. Sort the list t in descending order.
3. Sum up the first c/2 elements where c is the count of elements in the list (guaranteed to be even).