Converting Code to work with vectors

Question

i would like to know how to convert this Binary Heap code to work with a vector of objects instead of a vector of integers.

Assuming the vector which was created is vector <int> elements;

BinHeap

void BinHeap::maxHeapify(unsigned int index)
{
    unsigned int left, right, maxx;
    left = 2*index;
    right = 2*index + 1;

    // Base case
    if (index == 0)
        return;

    // Check the children, if they exist and pick the larger for swapping
    if (left < elements.size() && elements[left] > elements[index])
        maxx = left;
    else
        maxx = index;

    if (right < elements.size() && elements[right] > elements[maxx])
        maxx = right;

    if (maxx != index)
        {
            int temp = elements[maxx];
            elements[maxx] = elements[index];
            elements[index] = temp;
            maxHeapify(maxx);
        }

    // Now check the parent, if it exists
    maxHeapify(index/2);
 }

Node class

class Node
{
    private:
        int     guestID;
        string  name;
        string  surname;
        string  season;
        int     year;
        int     nights;
        string  payMethod;
        string  purpose;
        string  membership;
        Node*   nextPtr;

    public:
            // Constructor function
        Node(int, string, string, string,int, int, string, string, string);

            //Accessor functions
        int     getID()         { return guestID; }
        string  getName()       { return name; }
        string  getSurname()    { return surname; }
        string  getSeason()     { return season; }
        int     getYear()       { return year; }
        int     getNights()     { return nights; }
        string  getpayMethod()  { return payMethod; }
        string  getPurpose()    { return purpose; }
        string  getMembership() { return membership; }
        Node*   getNext()       { return nextPtr; }
        string  getData();

            //Mutator functions
        void setID(int num)              { guestID = num; }
        void setName(string str)         { name = str; }
        void setSurname(string str)      { surname = str; }
        void setSeason(string str)       { season = str; }
        void setYear(int yr)             { year = yr; }
        void setNights(int totNights)    { nights = totNights; }
        void setpayMethod(string payment){ payMethod = payment; }
        void setPurpose(string str)      { purpose = str; }
        void setMembership(string str)   { membership = str; }

        void setNext(Node* ptr){nextPtr = ptr;}
};

Any help would be greatly appreciated

I hope the point of this exercise was to learn about templates. It is a great exercise for learning about templates. But assuming it is, don't ask for someone to do it for you. Try changing your BinHeap from an ordinary class to a templated class and changing the relevant uses of `int` to the template parameter. If you get stuck, post what you tried and ask a more specific question. — JSF, Nov 18 '15 at 13:44
It wasn't about learning template. In another function i got the node vector to work, but because the vector is an and not a i wasn't able to get the maxHeapify modified. — ImmortalBajan, Nov 18 '15 at 13:49
You **could** write a version of BinHeap which only supports elements of type `node`, just as you currently have a version of BinHeap that only supports elements of type `int`. Taking this opportunity to use some templating would be better. Either way, you first need a comparison operator. It is likely simplest to define a typical `operator<` as a member of node and use that. Passing a `less` functor into the construction of the heap is more general, but enough harder (for little benefit) that I think you should skip that for now. — JSF, Nov 18 '15 at 13:55
I will follow this http://www.tutorialspoint.com/cplusplus/cpp_templates.htm and hopefully i should get it working, thanks for the help — ImmortalBajan, Nov 18 '15 at 13:58
I notice you compare elements with `elements[left] > elements[index]` I suggest you change that to `elements[index] < elements[left]`. You could instead define `operator>` in your node class, but there is quite a bit of value in following general conventions and the convention for comparing arbitrary objects is to prefer `<` — JSF, Nov 18 '15 at 14:02
Also notice your recursive calls in `maxHeapify` are excessive. You are making it recheck positions it should already know are correct. The performance would still be the same "Order" (it isn't such a bad flaw that you change O(logN) operations into O(N)) but it does change the average case to be slightly worse than the worst case should have been. — JSF, Nov 18 '15 at 14:07
do you have an example of how to create the operator< method? Would it be like. bool operator<(what to put here?, what to put here?); — ImmortalBajan, Nov 18 '15 at 15:36

score 0 · Answer 1 · edited May 23 '17 at 11:59

Partial answer (since code is so hard to put in comments):

class Node
{
   ...
   bool operator<( Node const& r ) const
   {
      return guestID < r.guestID;
   }
   ...
};

That makes the crude guess that you want to base Node comparison entirely on a single member of Node. In the more likely case that you want to base it on a prioritized sequence of members, use std::tie as shown in:

Implementing comparison operators via 'tuple' and 'tie', a good idea?

Notice that link shows an operator< that is not a member of the class being compared, while I showed the (usually more convenient) form of one that is a member. But that shouldn't change much about the way std::tie should be used.

In the member form of operator< the left hand operand is the one implicitly passed *this so members simply named are from the left, while the named parameter (r in my sample code) is the right hand operand.

There are many rules for a valid "less than" relationship, which operator< should achieve. There is no C++ rule requiring operator< to achieve that, but many possible uses (including your heap) will be unsound if you fail to have a valid "less than" relationship. If you will be checking multiple members in comparing two Nodes, it is very common (almost universal) for beginners to get that wrong and accidentally define an invalid "less than". But if you let std::tie manage the prioritized list of sub comparisons, you easily leverage valid relationships in the operator< of each member into an automatically valid relationship in the overall comparison.

Correct me if im wrong, this code accepts a node, and it compares the previous guestID with the guestID of the node that is being passed in and returns true when previous guestID is less than the current one? — ImmortalBajan, Nov 18 '15 at 16:02
This code accepts **two** `const Node`s, (not "a node"). As with other member functions, one `Node` (which happens to be the left operand where the `<` is used) is taken implicitly and isn't shown in the list of operands. The one Node shown in the list of operands is the right hand one of the two used with the actual `<` — JSF, Nov 18 '15 at 16:26

score 0 · Answer 2 · answered Nov 22 '15 at 23:22

0

Found my answer, i was thinking too complex, all i had to do was use the .getID() functions and add a default constructor to fix another issue

answered Nov 22 '15 at 23:22

ImmortalBajan

13
5

Converting Code to work with vectors

2 Answers2