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

Question

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.

Answer 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 floats 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();        
  }
  

Demo