Implementation of binary min-heap data structure

Question

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;
    }


}

Answer 1

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.

Answer 2

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.

Answer 3

• 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;
  }