14
\$\begingroup\$

What do you think is wrong with this code, and how can it be improved? What corner case have I overlooked, if any?

Note: I do not want to use any STL features here, but I'm okay with anything else from C++11.

class min_heap{
    int pvt,P;
    int arr[10000];
public:

    min_heap(){
        P=1;
    }
    void add(int x){
        pvt=P;
        arr[P]=x;

        while(pvt>1){
            if(arr[pvt]<arr[pvt/2]){
                int temp=arr[pvt];
                arr[pvt]=arr[pvt/2];
                arr[pvt/2]=temp;
                pvt=pvt/2;

            }
            else
                break;
        }
        P++;
    }

    int extract(){
        int ans=arr[1];
        arr[1]=arr[P-1];
        int elm=arr[1];
        int x=1;
        while(x*2+1<=P-1){
            int exc=1;
            int temp=arr[x];

            if(arr[x*2]>arr[x*2+1]&&(elm>arr[x*2]||elm>arr[x*2+1])){
                arr[x]=arr[x*2+1];
                arr[x*2+1]=temp;
                x=x*2+1;
                continue;
            }
            if(arr[x*2]<=arr[x*2+1]&&(elm>arr[x*2]||elm>arr[x*2+1])){
                arr[x]=arr[x*2];
                arr[x*2]=temp;
                x=x*2;
                continue;
            }
            break;

        }
        if(P-1>=x*2&&arr[x*2]<arr[x]){
            int temp=arr[x];
            arr[x]=arr[x*2];
            arr[x*2]=temp;
        }
        P--;
        return ans;
    }
};


int main()
{
    min_heap min1;
    for(int i=1;i<=50;i++)
    {
        int x1;
        std::cin>>x1;
        min1.add(x1);
    }
    std::cout<<std::endl;
    for(int i=1;i<=50;i++){
        int x1=min1.extract();
        std::cout<<x1<<std::endl;
    }


}
\$\endgroup\$
6
  • \$\begingroup\$ This contains no C++11 code, yet it is tagged as that. Does that mean you're willing to accept such recommendations? \$\endgroup\$
    – Jamal
    Jul 18, 2014 at 12:56
  • \$\begingroup\$ No , i don't want to use any STL features to implement a minheap if that's what you ment. \$\endgroup\$ Jul 18, 2014 at 12:59
  • \$\begingroup\$ I just meant anything added under C++11 (such as the auto keyword and nullptr). \$\endgroup\$
    – Jamal
    Jul 18, 2014 at 13:00
  • \$\begingroup\$ yeah anything like that is fine. \$\endgroup\$ Jul 18, 2014 at 13:02
  • 1
    \$\begingroup\$ You do know there is already a heap in the STL? make_heap, push_heap and pop_heap \$\endgroup\$ Jul 18, 2014 at 16:55

3 Answers 3

15
\$\begingroup\$

You've mentioned that you don't want to utilize the STL, so I'll honor that. Just be aware that neglecting to use it may lessen the quality of your code, especially if you start to experience bugs.

I'll mainly address best-practices as I'm not so familiar with the algorithm myself.

  • Your lack of whitespace just makes this painful to read. If a line appears to be too long, it either needs to be shortened (preferred) or wrapped onto separate lines.

    Either way, you should especially have some whitespace between operators and operands so that it won't take others unneeded time to read and understand it. This will also benefit you whenever you're maintaining the code (fixing bugs, adding things, and changing things around).

    For instance, this line:

    if(arr[x*2]>arr[x*2+1]&&(elm>arr[x*2]||elm>arr[x*2+1])){
    

    should look like this:

    if (arr[x*2] > arr[x*2+1] && (elm > arr[x*2] || elm > arr[x*2+1])) {
    

    Isn't that easier to read? There's no need to cram everything together; just let the code breathe. You could still space out the operators within the [], but it's not quite as common.

  • Your variable names are very generic. Many of them are only single letters, and your array data member is just named arr. Without good naming, you'll just leave others guessing at what each variable does. Plus, if you look at this code years from now, you may have no idea what it all means, and so you may be tempted to throw it away and start all over.

  • Although it's entirely optional, you can add the private keyword anyway, even though classes are private by default. It may add a little more readability, especially if there is a lot of code.

  • The constructor:

    min_heap(){
        P=1;
    }
    

    can be an initializer list:

    min_heap() : P(1) {}
    

    If it ever gets lengthy, you can list the members on separate lines:

    min_heap()
        : P(1)
        , // additional ones
        , // separated by commas
    {}
    

    If pvt and arr need to be initialized, then it should be done here as well. I'm not sure why you just initialize one data member.

  • You don't need std::endl here. In most cases, a flush isn't necessary along with a newline, which is what's being done by that.

    Instead, just output "\n" for a newline:

    std::cout << "\n";
    

    This is also mentioned here.

Overall, I'd highly recommend making this more readable first, so that it's easier to understand and improve for yourself and others. Implementing all the algorithms yourself will especially require the code to be clean and self-documenting, otherwise you're really just writing C code instead.

\$\endgroup\$
3
  • \$\begingroup\$ @Randomizer: You're welcome. You've accepted this early, so I assume this is specifically the kind of advice you were seeking. You may improve on all these things and post a new question with better code, otherwise you may wait for more possible answers first. \$\endgroup\$
    – Jamal
    Jul 18, 2014 at 13:59
  • \$\begingroup\$ I was searching for advise basically to make my code more readable and free from bugs i have received that complain i don't write very readable code ,I knew how to implement this using STL (Thanks for the edit ). I will be using a code similar to this to write dijstra and i will put that up for a review. \$\endgroup\$ Jul 18, 2014 at 14:23
  • 2
    \$\begingroup\$ @Randomizer: That's fine. If you'd like to avoid bugs, then you can at least use a storage container, such as std::vector mentioned by Jerry. They take nothing from your algorithms, and they are much safer than C-style arrays. \$\endgroup\$
    – Jamal
    Jul 18, 2014 at 14:25
14
\$\begingroup\$
  1. Your names. pvt is pretty poor and P is, frankly, quite dismal as names go. I'm still not sure what P is really supposed to mean.
  2. you've used a fixed-size array where it's not really suitable. If your heap contains fewer than 10000 items, it wastes space. If a user tries to add more than 10000 items, they overflow the space you've allocated, leading to undefined behavior. Much better to use (for example) a std::vector that will grow the allocation as needed to approximate the size actually in use.
  3. Writing your own code to exchange items:

        int temp=arr[x];
        arr[x]=arr[x*2];
        arr[x*2]=temp;
    

    ...is almost never as expressive as using std::swap to do the job. I find std::swap(arr[x], arr[x*2]); much more readable. If you want to support using a specialized swap in case the user has provided one for the type being stored, you can use an idiom like:

    using std::swap;
    
    swap(arr[x], arr[x*2]);
    

    This way if there's a swap for the type of arr[x] (defined in the same namespace as that type) it'll be found via Koenig lookup and used for the swap. If that doesn't exist, then std::swap will be found because of the using declaration.

  4. Your current code is limited to storing ints in the heap for no particularly good reason. About the only real requirement for a heap is that items satisfy a strict weak ordering (you must be able to compare them, and comparisons must be transitive so if a<b and b<c, then a<c).

  5. along the same lines, you could allow the user to specify a function/object to use to compare items. This allows you to use the same code for either a min-heap or a max-heap by simply changing the comparison.
  6. Bonus: Ideally, I'd probably prefer to access the heap via iterators so I could use it with standard algorithms and such.

Based on those, I'd prefer to see the skeleton of the code look something like this:

template <class T, class cmp=std::less<T>>
class heap {
    std::vector<T> data;
public:
    heap();

    template<class Iter>
    heap(Iter b, Iter e); // construct a heap from the elements pointed to by two iterators

    void insert(T);

    T extract();
};

I should probably note that the T extract(); has a potential problem with exception safety. I've assumed (for the moment) that the type being stored never throws on copy/move. If it could throw on copy/move, then T extract() wouldn't be exception safe. The problem is much the same as a pop from a stack that returns the popped value: if the copy/move to return the item throws an exception, the user doesn't receive the item, but the item has already been removed from the heap, so the item is lost and can't be retrieved.

If T might throw exceptions on copy/move, you typically want to change the interface to something more like:

T get_min();  // just retrieves smallest item, without removing it from the heap.
void pop(); // just removes smallest item

This lets the user retrieve the smallest item, then if and only if that succeeds, remove the smallest item from the heap. Oddly, they don't need to check for that succeeding though:

T x = myheap.get_min();
myheap.pop();

If the first statement throws an exception, then the second statement won't execute, and the heap remains unchanged. If the first doesn't throw, then the second executes with (presumably) no chance of throwing.

That last condition raises another point, however: in nearly every case, you need some assurance about at least a few operations not throwing. In this case, we depend on being able to swap items without ever throwing, or we can't remove an item from the heap dependably--if swapping might throw, then attempting to remove an item could corrupt the heap.

\$\endgroup\$
7
  • 1
    \$\begingroup\$ Be aware that the OP doesn't want to utilize the STL for this (as such, the OP's code might as well be done in C instead, but whatever). \$\endgroup\$
    – Jamal
    Jul 18, 2014 at 13:47
  • \$\begingroup\$ None of what I envision would be using what's built into the standard library except for a raw container (vector, deque, etc.) It's mostly just writing new code that works along the same lines as what's in the standard library. If he wants to write his own expandable container, more power to him--I'm just not ambitious enough to do it for an answer (doing that well is definitely not trivial). \$\endgroup\$ Jul 18, 2014 at 13:50
  • 1
    \$\begingroup\$ Yeah, std::vector is the biggest thing, and I was about to recommend it. Luckily, it can just be disregarded if it really does count as well. I personally find it best to at least use that, since it doesn't take away with writing out algorithms. \$\endgroup\$
    – Jamal
    Jul 18, 2014 at 13:52
  • \$\begingroup\$ Thanks for your help jerry , could you please elaborate on point 4 . \$\endgroup\$ Jul 18, 2014 at 14:26
  • 2
    \$\begingroup\$ @Snowbody: actually double is kind of a special case: NaNs break things that require ordering (a NaN doesn't even compare equal to itself, which can break a lot of assumptions about how comparisons must work). \$\endgroup\$ Jul 18, 2014 at 14:33
6
\$\begingroup\$
  • A cluttered class definition is as bad as a cluttered global namespace. The only things in there should be the things that have to be there. In this case, there is no reason for pvt to be a class member; it is only used in add() and should be a local variable.

  • The expression

    (arr[x*2] > arr[x*2+1] && (elm > arr[x*2] || elm > arr[x*2+1])
    

    can and should be simplified. Because of a short-circuit behaviour of &&, by the time we are dealing with elm it is already known that arr[x*2] > arr[x*2+1]. Therefore there's no need to compare it with arr[x*2].

  • As mentioned above, swapping should be factored out into a method.

  • The continue/continue/break flow makes it very hard to follow. The loop body needs streamlining.

  • Similarly, I'd recommend streamlining the add() loop as

    while(pvt > 1 && arr[pvt] < arr[pvt/2]) {
        swap(arr, pvt, pvt/2);
        pvt = pvt/2;
    }
    
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.