CODEWITHSUNDEEP
c++algorithmheap
bartekmp
bartekmp

Reputation: 413

Own heap implementation in C++

I have to write my own implementation of heap in C++, which stores objects of type:

std::pair<City, int>

where City is a structure to store two integers, which represent city coords and string - city name. I do know how to do this with plain integers, but using pair of values is a little problematic to me. I've already started to write my heap class, but, as I said, I don't know how to do this with those pairs. I want the heap to be sorted by the int value of the pair.

Upvotes: 1

Views: 692

Answers (3)

TemplateRex
TemplateRex

Reputation: 70526

You could try to use std::make_heap which will put a sequence of your pairs into a heap order, see this online example. To sort by the int value only, use a C++11 lambda expression that will compare the second element of each pair

Alternatively, given that you cannot use any STL heap-related algorithms, but given any self-made implementation of

template<typename RandomIt>
void my_make_heap(RandomIt first, RandomIt last)
{
     /* some algorithm using `a < b` to do comparisons */
}

you can rewrite it as (or add an overload)

template<typename RandomIt, typename Compare>
void my_make_heap(RandomIt first, RandomIt last, Compare, cmp)
{
     /* SAME algorithm, but now using `cmp(a, b)` to do comparisons */
}

and then call it as my_make_heap(first, last, int_cmp) where the lambda expression compares pairs like this:

    typedef std::pair<City, int> Element;
    auto int_cmp = [](Element const& lhs, Element const& rhs) {
         return lhs.second < rhs.second;
    };

Upvotes: 2

Spandan
Spandan

Reputation: 2138

So from what i understand :

Your structure is something like this ,

struct node
{
   int X_coord;
   int y_coord;
   string name;
}

And you need to form the Heap based on "int' value of pair ,call it 'x' .

So your pair is 

pair<node n , int x> ;

This , is a very readable code for Heap , implemented in a class.

It can be easily modified to your requirement for pair<> value . Just use , "heap.second" as your key value .

Upvotes: 1

Angew is no longer proud of SO
Angew is no longer proud of SO

Reputation: 171127

If you know how to do it for ints, you're almost there. Treat the pair objects just as you would treat ints when assigning, but for comparison purposes, use .second instead of the value directly.

Upvotes: 5

Related Questions