Return to Answer

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)
  {}

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

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_));

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)
  {}

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

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_));