Implementation of binary heap in C++

Question

Things I can think of include integer overflow, if the input type is int, etc. But other than that, what do you think is wrong with this code, design-wise, style-wise, and also in terms of other edge/corner cases?

binaryheap.h

#ifndef INCLUDE_BINARYHEAP_H_
#define INCLUDE_BINARYHEAP_H_

#include <vector>
#include <iterator>
#include <cmath>

// Assume min heap
template <class T>
class BinaryHeap
{
 private:
  unsigned long heap_size_;
  std::vector<T> data_;
  // typedef typename std::vector<T>size_type heap_size_;
  void SiftUp(unsigned long node);
  void SiftDown(unsigned long node);

 public:
  BinaryHeap(unsigned long num_elements);
  BinaryHeap();
  ~BinaryHeap() {}

  // Misc Operations (using STL namimg).
  unsigned long count() { return heap_size_;}  // Get count of objects.
  void clear();                      // clear the object for reuse.

  // Main operations allowed by the data structure.
  template <class I>
  int Heapify(I start, I end);
  const T FindXtrma();
  const T ExtractXtrma();
  void Insert(const T& data);   // Insert(key)
  void Delete(unsigned long element);     // Delete(element)
  void IncreaseKey(unsigned long element, const T& change);
  void DecreaseKey(unsigned long element, const T& change);
  unsigned long get_size(){return(heap_size_);}
  /* void Merge(class &Heap); */
};

#endif  // INCLUDE_BINARYHEAP_H_

binaryheap.cpp

#include <binaryheap.h>
#include <vector>
#include <algorithm>

template <class T>
BinaryHeap<T>::BinaryHeap(unsigned long num_elements)
{ heap_size_ = num_elements;
  data_.reserve(num_elements);
}


template <class T>
BinaryHeap<T>::BinaryHeap()
{ heap_size_ = 0;
}

template <class T>
void BinaryHeap<T>::SiftDown(unsigned long node)
{ unsigned long lchild = 2*node+1;
  unsigned long rchild = 2*node+2;

  bool rexists = rchild < heap_size_;
  bool lexists = lchild < heap_size_;
  if (!lexists && !rexists) return;
  bool left_small;
  if (rexists && data_[lchild] > data_[rchild])
    left_small = false;
  else
    left_small = true;

  if (data_[lchild] < data_[node] && left_small)
  { std::swap(data_[node], data_[lchild]);
    SiftDown(lchild);
  }
  else if (data_[rchild] < data_[node] && rexists && !left_small)
  { std::swap(data_[node], data_[rchild]);
    SiftDown(rchild);
  }
}

template <class T>
void BinaryHeap<T>::SiftUp(unsigned long node)
{ long parent = floor(node/2)-(node+1)%2;
  bool pexists = parent >= 0;
  if (pexists && data_[parent] > data_[node])
  { std::swap(data_[parent], data_[node]);
    SiftUp(parent);
  }
}

template <class T>
template <class I>
int BinaryHeap<T>::Heapify(I start, I end)
{ unsigned long d = std::distance(start, end);
  if (data_.size() != 0)
    this->clear();
  if (heap_size_ == 0)
    heap_size_ = d;
  // may be warn them.
  if (d != heap_size_)
    heap_size_ = d;
  for (I i = start; i != end; ++i)
    data_.push_back(*i);
  for (unsigned long i = heap_size_-1; i <= heap_size_; --i)
  { SiftDown(i);
  }
  return 0;
}

template <class T>
const T BinaryHeap<T>::FindXtrma()
{ if (heap_size_ <= 0)
    return ((T)(0));
  return data_.front();
  // return this->data_[0];
}

template <class T>
const T BinaryHeap<T>::ExtractXtrma()
{ if (heap_size_ <= 0)
    return ((T)(0));
  T max_value = data_.front();
  std::swap(data_.front(), data_.back());
  data_.pop_back();
  --heap_size_;
  SiftDown(0);
  return max_value;
}

template <class T>
void BinaryHeap<T>::Insert(const T& new_node)
{ data_.push_back(new_node);
  SiftUp(data_.size()-1);
  ++heap_size_;
}

template <class T>
void BinaryHeap<T>::Delete(unsigned long element)
{ if (element >= heap_size_)
    return;
  std::swap(data_[element], data_.back());
  data_.pop_back();
  --heap_size_;
  SiftUp(element);
  SiftDown(element);
}

template <class T>
void BinaryHeap<T>::IncreaseKey(unsigned long element, const T& change)
{ data_[element] = data_[element]+change;
  SiftDown(element);
}

template <class T>
void BinaryHeap<T>::DecreaseKey(unsigned long element, const T& change)
{ data_[element] = data_[element]-change;
  SiftUp(element);
}

template <class T>
void BinaryHeap<T>::clear()
{ if (data_.size()  > 0)
    data_.clear();
}

template class BinaryHeap<int>;
template class BinaryHeap<float>;
template class BinaryHeap<unsigned int>;
template class BinaryHeap<long>;


template int BinaryHeap<int>::Heapify(std::vector<int>::iterator, std::vector<int>::iterator);
template int BinaryHeap<float>::Heapify(std::vector<float>::iterator, std::vector<float>::iterator);
template int BinaryHeap<unsigned int>::Heapify(std::vector<unsigned int>::iterator, std::vector<unsigned int>::iterator);
template int BinaryHeap<long>::Heapify(std::vector<long>::iterator, std::vector<long>::iterator);

binaryheap_gtest.cpp

#include <binaryheap.h>
#include <vector>
#include "gtest/gtest.h"

using namespace std;

namespace
{ template<class T>
  class BHeapTest : public ::testing::Test
  {
   public:
    BinaryHeap<T> b1;
    BHeapTest() { b1 = BinaryHeap<T>(1000);}
    virtual ~BHeapTest() {}

   protected:
    vector<T> data_;
    virtual void SetUp()
    {
      unsigned long max_val = 2000;
      for (T i = 1000; i < (T)max_val; ++i)
        data_.push_back(i);
      b1.Heapify(data_.begin(), data_.end());
    }
    virtual void TearDown()
    { data_.clear();
    }
  };

  typedef ::testing::Types<int, unsigned int, long> MyTypes;
  TYPED_TEST_CASE(BHeapTest, MyTypes);

  TYPED_TEST(BHeapTest, SimpleTest)
  { EXPECT_EQ(1000, this->b1.FindXtrma());
    EXPECT_EQ(1000, this->b1.get_size());
    this->b1.Insert(3000);
    EXPECT_EQ(1000, this->b1.FindXtrma());
    EXPECT_EQ(1001, this->b1.get_size());
    this->b1.Delete(0);
    EXPECT_EQ(1001, this->b1.FindXtrma());
    EXPECT_EQ(1000, this->b1.get_size());
    this->b1.DecreaseKey(999, 1000);
    EXPECT_EQ(999, this->b1.FindXtrma());
    EXPECT_EQ(1000, this->b1.get_size());
    this->b1.IncreaseKey(0,1000);
    EXPECT_EQ(1001, this->b1.FindXtrma());
    EXPECT_EQ(1000, this->b1.get_size());
  }

  TYPED_TEST(BHeapTest, ComplexTest)
  { EXPECT_EQ(1000, this->b1.FindXtrma());
    EXPECT_EQ(1000, this->b1.get_size());
    for (int i = 0; i < 10; ++i)
      this->b1.ExtractXtrma();
    EXPECT_EQ(1010, this->b1.FindXtrma());
    EXPECT_EQ(990, this->b1.get_size());
    for (int i = 0; i < 10; ++i)
      this->b1.ExtractXtrma();
    EXPECT_EQ(1020, this->b1.FindXtrma());
    EXPECT_EQ(980, this->b1.get_size());
    this->b1.Insert(3232);
    EXPECT_EQ(981, this->b1.get_size());
  }
}  //  namespace

int main(int argc, char **argv)
{ ::testing::InitGoogleTest(&argc, argv);
  return RUN_ALL_TESTS();
}

Answer 1

Since you seem to be tryingy to mimic the style of STL containers (at least, that's what your comments say), there are several things you could improve:

STL containers subtypes

Most of the STL containers have subtypes. I am pretty sure that some parts of the standard library use these subtypes. Therefore, if you want your code to work with the generic algorithms, you better add those subtypes:

• value_type: probably be an alias for T, or std::vector<T>::value_type.
• size_type: in your case, it would be unsigned long since it is the type you use for the size of your heap. Generally, the type std::size_t is used for size_type though. The best solution in your case would be std::vector<T>::size_type
• reference: often T&.
• There are many other subtypes. Look at the documentation for std::vector and see which one you can take from the underlying std::vector and which one you better let alone (for example, you don't provide anything to work with iterators and you don't provide any mechanism for allocators).

Size of the heap

First of all, you have two functions to obtain the size of your heap, count and get_size, which is redundant. count is there so that your heap looks like an STL container, however, the standard method name to get the size of a container is size, not count. There is no need for the function get_size: it is a duplicate, it does not conform to STL naming, and it does not even conform to the case of your other functions.

I find the fact that the size of your heap does not correspond to the size of the underlying std::vector rather troubling. When I write this:

BinaryHeap<int> foo(8);

I know that enough memory has been reserved for 8 elements, but I would expect the size to be 0. Moreover, if I write this:

BinaryHeap<int> foo(8);
foo.FindXtrma();

I then have no idea what my value will be since the size is 8 and I did not control the inserted values. Generally speaking, you probably should implement size like this to avoid surprises:

size_type size() const
{
    return data_.size();
}

There are probably other things which could be improved: make your BinaryHeap more like a STL container by enabling a support for allocators for example (you could forward the allocator stuff directly to the underlying std::vector to avoid having to actually handle them). Also, instead of a real container, you could try to make your BinaryHeap a container adapter (like std::stack or std::queue) so that it can use an std::vector or an std::deque (or any conforming container).

Miscellaneous C++ stuff

It has been more than a year since the review, but it seems that it has some views, so I thought that it could be a good idea to complete it with some miscellaneous additional comments...

• You have template code in a .cpp file, this is really error-prone since templates are not compiled (their specializations are instantiated and compiled when needed). If you want to write a template library with separate interface and implementation, then put the interface in a .h file and include a .inl or .tpp file at the end of the header (these are the most common extensions for "implementation header files") with the implementation.

• You should const-qualify functions that do not alter the state of the class. For example, count (or size as I mentioned before) does not alter the heap and can be const-qualified to document that.

• Sometimes, your names should be more explicit. For example, template <class I> isn't explicit enough. It is easy to guess that it accepts iterators, but which kind of iterators? From the implementation, I think that it can accept forward iterators, so you should use names which reflect that fact:

  template <class ForwardIterator>
  int Heapify(ForwardIterator start, ForwardIterator end);
  

• By the way, this function does not return anything useful, it always return 0, which is at best useless and at worst confusing (and undocumented). The best thing to do is to make your function return void so that it is clear that it isn't returning anything:

  template <class ForwardIterator>
  void Heapify(ForwardIterator start, ForwardIterator end);
  

• You can replace this loop:

  for (I i = start; i != end; ++i)
      data_.push_back(*i);
  

  ...by a call to std::copy from the standard header <algorithm> with std::back_inserter to automatically perform the calls to push_back on the data_.

  std::copy(start, end, std::back_inserter(data_));
  

• Whenever possible, try to initialize what you can into a constructor initialization list instead of initializing things in the constructor body. Take for example this constructor:

  template <class T>
  BinaryHeap<T>::BinaryHeap(unsigned long num_elements)
  { heap_size_ = num_elements;
    data_.reserve(num_elements);
  }
  

  It is trivial to initialize heap_size_ from the initialization list, and feeding an integer to an std::vector constructor will actually be equivalent to a call to reserve. That means that you can write this constructor as:

  template <class T>
  BinaryHeap<T>::BinaryHeap(unsigned long num_elements):
      heap_size_(num_elements),
      data_(num_elements)
  {}
  

• This boolean initialization looks rather complicated:

  bool left_small;
  if (rexists && data_[lchild] > data_[rchild])
    left_small = false;
  else
    left_small = true;
  

  You can make a one-liner out of it which shouldn't be harder to read:

  bool left_small = !(rexists && data_[lchild] > data_[rchild]);
  

  You can even change it a little bit to remove the leading operator!:

  bool left_small = !rexists || data_[lchild] <= data_[rchild];
  

Answer 2

There is an error in the code:

if (data_[rchild] < data_[node] && rexists && !left_small)

You have to check rexists before data_[rchild]:

if (rexists && !left_small && data_[rchild] < data_[node])