current community

your communities

more stack exchange communities

Stack Exchange
tour help
Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.
up vote 6 down vote favorite

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();
}
share|improve this question
add comment

1 Answer

up vote 6 down vote accepted

Since you try 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 library uses these subtypes. So, 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.

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

BinaryHeap<int> foo(8);

I know that the 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 use 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). 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 a std::vector or a std::deque (or any confirming container).

share|improve this answer
    
Mimicking style of STL containers : I was not exactly intending that you thought. I was following Google Style Guide and the naming convention for getter and setter functions (or other simple functions) was an exception to their rule, and I was following the STL style naming. But your suggestion is a welcome change. Thanks for the nice review, will incorporate most of it. –  sumodds Mar 4 at 0:30
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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