TransWikia.com

I am fairly new to STLs in C++ and i tried making a heap using vectors. Didnt get the desired output

Stack Overflow Asked by user11880529 on December 9, 2021

#include<bits/stdc++.h>
using namespace std;
class Heap
{
    vector <int> v;
    int length;
public:
    void create(vector <int> v, int s);
    void display();
};
void Heap::create(vector <int> v, int s)
{
    length=s+1;
    for(int i=1;i<=s;i++)
    {
        this->v[i]=v[i-1];
    }
    int temp;
    int j;
    for(int i=2;i<length;i++)
    {
        temp=v[i];
        j=i;
        while(j>1&&temp>v[j/2])
        {
            swap(v[j],v[j/2]);
            j=j/2;
        }
        if(j==1)
        {
            v[j]=temp;
        }
    }
}

void Heap::display()
{
    for(int i=1;i<length;i++)
    {
        cout<<v[i]<<"t";
    }
    cout<<endl;
}

int main()
{
    vector <int> v;
    int ans=1;
    int d;
    while(ans==1)
    {
        cout<<"Enter the Datan";
        cin>>d;
        v.push_back(d);
        cout<<"Do you want to enter more data?n";
        cin>>ans;
    }
    cout<<endl;
    Heap h;
    h.create(v,((int)v.size()));
    h.display();
}

When i execute this code, it asks me to enter the data value. i enter all the data values i want to enter and click the enter button. it shows segmentation error. also the execution is taking a lot of time which is very unusaul. i use codeblocks version 20.

3 Answers

This is obviously a school exercise. So I will only give you pointers as to where your code goes wrong.

class Heap
{
    // vector <int> v;  // v is not a suitable name for a class member, it's too short 
    // int length;  // why length ?  Your container declared above has length information, using 
                    //  a duplicate can only introduce opportunities for bugs!!! 
    vector<int> heap;  // I've also renamed it in code below
public:
    void create(vector <int> v, int s);
    void display();
};

// some documentation is needed here...
// A I read it, it should be something like this, at least (this may reveal some bug):
//
// Initializes heap from range [v[1], v[s])
// void Heap::create(vector <int> v, int s) // you do not need a copy of the source vector!
void Heap::create(const vector& <int> v, int s)  // use a const reference instead.
{
    // This is not how you assign a vector from a range
    // length=s+1;
    // for(int i=1;i<=s;i++)
    // {
    //    this->v[i]=v[i-1];
    // }

    // check inputs always, I'll throw, but you should decide how to handle errors
    // This test assumes you want to start at v[1], see comment below. 
    if (0 > s || s >= v.size())
        throw std::out_of_range ("parameter 's' is out of range in Heap::Create()"); 

    // assign our private storage, why the offset by '1' ????
    // I doubt this is a requirement of the assignment.
    heap.assign(v.begin() + 1, v.begin() + s + 1);

    //int temp;  // these trivial variables are not needed outside the loop.
    //int j;

    // why '2' ?? what happens to the first element of heap?
    // shouldn't the largest element be already stored there at this point?
    // something is obviously missing before this line. 
    // you'll notice that v - the parameter - is used, and heap, our 
    // private storage is left unchanged by your code.  Another hint
    // that v is not suitable for a member name.  
    for(int i = 2; i < v.length(); i++)
    {
        int temp = v[i];   // temp defined here

        int j = i;
        //while(j > 1 && temp > v[j/2])  // avoid using while() when you can use for().
        //{
        //    swap(v[j],v[j/2]);
        //    j=j/2;
        //}

       // This is your inner loop. it does not look quite right   
       for (; j > 1 && temp > v[j / 2]; j = j / 2)
           swap(v[j], v[j/2]);

       if (j == 1)
           v[j] = temp;
    }   
}

void Heap::display()
{
    for(int i=1;i<length;i++)
    {
        cout<<v[i]<<"t";
    }
    cout<<endl;
}

From reading your code, it seems you forgot that vectors are zero-based arrays, i.e. The first element of vector v is v[0], and not v[1]. This creates all kinds of near unrecoverable errors in your code.

As a matter of personal preference, I'd declare Heap as deriving publicly from std::vector, instead of storing data in a member variable. Just something you should consider. You could use std::vector<>::at() to access and assign elements within the object.

As is, your code will not function correcly, even after fixing the memory access errors.

Answered by Michaël Roy on December 9, 2021

When i execute this code, it asks me to enter the data value. i enter all the data values i want to enter and click the enter button

Yeah, I'm not interested in guessing what you typed in order to reproduce your problem. I'm also not interested in guessing whether the issue is in your I/O code or the code you think you're testing.

Always remove interactive input when you're preparing a minimal reproducible example so that other people can actually reproduce it.

Sometimes removing the interactive input may fix your problem, in which case you've learnt something important (and probably want to ask a different question about your input code).

it shows segmentation error

A segmentation fault interrupts your program at the exact point where it happens. If you run your program in a debugger, it will show you where this is, and the state of everything in your program when it happened. You should try this, and learn to use your debugger.

        this->v[i]=v[i-1];

As correctly pointed out in the other answer, there is a bug on this line. You correctly called push_back when reading input, so you could just do the same here. Alternatively you need to explicitly size this->v before indexing elements that don't exist.

The other main problem with this function is that it mixes up this->v (used, illegally, only once on the line above) and v which is a local copy of the v in main, and which goes out of scope and is lost forever at the end of the function.

Just give your variables different names so you don't have to write this->v on all the other lines where you currently refer to v. Also, consider passing the original v by const ref instead of making a copy.

NB. I do see and understand that you're deliberately switching to 1-based indexing for the sort. If for some reason you can't just use std::sort or std::make_heap, you could at least explicitly set the zeroth element to zero, and then just std::copy the rest.

Finally, Heap::create really looks like it should just be a constructor. Forcing two-phase initialization is poor style in general, and I don't see any reason for it here.

Answered by Useless on December 9, 2021

First issue: you have used 'this->v' before initializing it. In this point:

 this->v[i]=v[i-1];

this->v have size 0 and has no element to be accessed via index; Furtheremore you have used wrong indices for it. Assuming this->v has initialized, correct index access is like this

 this->v[i-1]=v[i-1];

Finally, it is better to sort the std vectors by using std::sort builtin function:

#include <algorithm>
std::sort(this->v.begin(), this->v.end());

Answered by Ali Askari on December 9, 2021

Add your own answers!

Ask a Question

Get help from others!

© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP