## How can I sort a vector<pair<pair<float, float>, unsigned int>> by the first float, and if there's a tie the second float?

Problem Description:

I have a priority queue with ‘keys’ that currently looks like this:

```
using HeapKey = pair<Cost, Cost>;
vector<pair<HeapKey, unsigned int>> U;
```

I insert in the queue with this command:

```
push_heap(U.begin(), U.end(), KeyCompare());
```

And I have a sorting command like this:

```
struct KeyCompare {
bool operator()(const pair<HeapKey, unsigned int>& a, const pair<HeapKey, unsigned int>& b) const
{
return a.first > b.first;
}
};
```

I haven’t worked with heaps very much, and my inexperience shows. I’ve read that heaps traditionally works by having the largest element first. I need the smallest.

But I also need the queue to be sorted by lexicographical order so that a key is less than or equal to another key if:

```
(k1.first <= k2.first) OR (k1.first == k2.first AND k1.second <= k2.second)
```

And I wonder how exactly I code that in C++? Currently my code doesn’t seem to work a 100% since mostly get the smallest element defined by the k1.first, but not always, and I need to implement that check of the second element if two keys are equal so I can sort my priority queue.

Thank you

**Edit:**

Sorry about the lack of code. Took me a little while but I think I have a good example with this:

```
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
using Cost = float;
using HeapKey = pair<Cost, Cost>;
vector<pair<HeapKey, unsigned int>> U;
struct KeyCompare {
bool operator()(const pair<HeapKey, unsigned int>& a, const pair<HeapKey, unsigned int>& b) const
{
return a.first > b.first;
}
};
ostream& operator<<(ostream& os, pair<Cost, Cost> const& p) {
return os << "<" << p.first << ", " << p.second << ">";
}
int main()
{
U.push_back({ {5.62843, 2.8}, 1 });
U.push_back({ {5.64264, 1.4}, 2 });
U.push_back({ {6.01976, 1}, 3 });
U.push_back({ {6.2, 5.2}, 4 });
U.push_back({ {6.03607, 3.8}, 5 });
U.push_back({ {6.03607, 3.8}, 6 });
U.push_back({ {7.45028, 3.8}, 13 });
U.push_back({ {7.45028, 3.8}, 14 });
U.push_back({ {7.45028, 3.8}, 15 });
U.push_back({ {5.62843, 1}, 16 });
U.push_back({ {5.02843, 7.8}, 17 });
push_heap(U.begin(), U.end(), KeyCompare());
cout << "U: ";
for (auto p : U) {
cout << p.second << p.first << " - ";
}
cout << endl;
for (int i = 0; i < 5; i++) {
pop_heap(U.begin(), U.end(), KeyCompare());
U.pop_back();
cout << U.front().second << U.front().first << endl;
}
}
```

So, what I get from this is:

```
U: 17<5.02843, 7.8> - 1<5.62843, 2.8> - 3<6.01976, 1> - 4<6.2, 5.2> - 2<5.64264, 1.4> - 6<6.03607, 3.8> - 13<7.45028, 3.8> - 14<7.45028, 3.8> - 15<7.45028, 3.8> - 16<5.62843, 1> - 5<6.03607, 3.8> -
1<5.62843, 2.8>
2<5.64264, 1.4>
16<5.62843, 1>
3<6.01976, 1>
6<6.03607, 3.8>
```

And the problem I believe I’m having is, as you can see, that after I pop elements 17 I have element 1 as the next. However, element 16’s first key is of equal size and it’s second key is smaller, so I would like that to go first.

Furthermore element 2 comes before element 16 and 16’s first key is smaller than element 2’s first key, so that’s not right.

Hope this is better.

## Solution – 1

- You are using the wrong function (
`std::push_heap`

) to create a max heap.`push_heap`

puts the last element in an already existing max heap in its correct place. Use`std::make_heap`

to create the heap.`std::make_heap(U.begin(), U.end(), KeyCompare());`

- The comparator needs to compare the second
`float`

before the first and possibly also the`unsigned int`

to get the job done properly. To make that easy, use`std::tie`

. If you for example want the smallest values extracted first:`#include <tuple> struct KeyCompare { bool operator()(const std::pair<HeapKey, unsigned int>& a, const std::pair<HeapKey, unsigned int>& b) const { return std::tie(a.first.second, a.first.first, a.second) > std::tie(b.first.second, b.first.first, b.second); } };`

The above is the same as you would get if you instead did it manually like below:

`struct KeyCompare { bool operator()(const std::pair<HeapKey, unsigned int>& a, const std::pair<HeapKey, unsigned int>& b) const { if(a.first.second > b.first.second) return true; if(a.first.second < b.first.second) return false; if(a.first.first > b.first.first) return true; if(a.first.first < b.first.first) return false; if(a.second > b.second) return true; return false; }`

To switch ascending/descending order, just flip the

`<`

/`>`

operators. When you use`std::tie`

, you can use members from both`a`

and`b`

to create each tuple. In the example below I’ve put`b.second`

in the first and`a.second`

in the last. The`float`

s will then be ordered in ascending order while the`unsigned int`

will be in descending order.`return std::tie(a.first.second, a.first.first, b.second) > std::tie(b.first.second, b.first.first, a.second);`

- You access the wrong element when you print out the result. The value to be popped from the heap is in
`U.back()`

after you’ve called`std::pop_heap`

, not in`U.front()`

. You can simply reorganize your code to do it properly:`while(not U.empty()) { std::cout << U.front().second << ' ' << U.front().first << 'n'; std::pop_heap(U.begin(), U.end(), KeyCompare()); U.pop_back(); }`