Ideas for specific data structure in c++

Question

I need to do some task. There are numbers give in two rows and they act like pairs of integers (a, b). I have to find the maximum 5 numbers of the a-row and then select the max of those 5 but this time from the b-row. Ex:

1 4
5 2
3 3
7 5
6 6
2 9
3 1

In this example, the pair i need is (6,6) because 6 (a) is in the top 5 of the a[i] numbers and 6 (b) is the maximum in the b section of those 5 pairs. I was thinking of doing this with vectors and my own defined structures, also use some temp arrays but i don't know if that's the right thing to do maybe there is simpler way to do this.

Any ideas ?

EDIT: I also need the index number of the pair (in the case that is 5, it's the fifth pair i.e).

Answer 1

A priority queue holding pairs that does its order evaluations based on the first element of the pair would be appropriate. You could insert all the pairs and then extract the top 5. Then just iterate on that list of pairs looking for the max of the second element of each pair.

edit

I should say that it is a decent solution only if you can accept a runtime on the order of O(n * lg n)

Answer 2

Alternate approaches:

Push triples (first, second, index) into a vector and then std::partial_sort the first 5 items using a descending order functor on the first element. Then use std::max_element with a second functor to find the max of the second element, and grab its index. If I'm reading the complexity of partial_sort correctly this should run in linear time (O(n)) because we're always sorting a max of 5 elements rather than O(n*log n).

Similarly, have the vector only contain pairs and sort a second vector containing indexes into the first one.