5
\$\begingroup\$

I implemented this max-heap to satisfy the C++ Container requirements. I am fairly confident I implemented bubble_up, bubble_down, and sort correctly. It passes for small sets of numbers I give it. If you're wondering what bubble_down(iterator, iterator) does, it does the bubble down action but ignores positions past last (inclusive). In sort, the vector becomes sorted from right to left, so as the root bubbles down it will not interact with the already sorted part. Also note that after sorting you will want to call build to rebuild the heap.

#include <iostream>
#include <string>
#include <vector>
#include <iterator>
#include <utility>
#include <sstream>
#include <cmath>

template<typename Type>
class max_heap {
public:
  using value_type = Type;
  using reference = Type&;
  using const_reference = const Type&;
  using iterator = typename std::vector<Type>::iterator;
  using const_iterator = typename std::vector<Type>::const_iterator;
  using difference_type = typename std::vector<Type>::difference_type;
  using size_type = typename std::vector<Type>::size_type;

  max_heap() = default;
  ~max_heap() = default;
  max_heap(iterator begin, iterator end);
  max_heap(const max_heap<Type>& other);
  max_heap(max_heap<Type>&& other);

  iterator begin();
  const_iterator begin() const;
  const_iterator cbegin() const;
  iterator end();
  const_iterator end() const;
  const_iterator cend() const;

  reference operator=(max_heap<Type> other);
  reference operator=(max_heap<Type>&& other);
  bool operator==(const max_heap<Type>& other);
  bool operator!=(const max_heap<Type>& other);
  void swap(max_heap& other);
  template<typename T>
  friend void swap(max_heap<T>& lhs, max_heap<T>& rhs);
  size_type size() const;
  size_type max_size() const;
  bool empty() const;

  void sort();
  void insert(value_type value);
  void remove(iterator elem);
  void remove_maximum();
  reference maximum();
  const_reference maximum() const;

  // build tree in linear time
  void build();

private:
  iterator parent_of(iterator child);
  iterator left_child_of(iterator parent);
  iterator right_child_of(iterator parent);
  void bubble_up(iterator elem);
  void bubble_down(iterator elem);
  void bubble_down(iterator elem, iterator last);

  std::vector<int> rep;
};

template<typename Type>
max_heap<Type>::max_heap(iterator begin, iterator end)
  : rep(begin, end) {
  build();
}

template<typename Type>
max_heap<Type>::max_heap(const max_heap<Type>& other)
  : rep(other.rep) { }

template<typename Type>
max_heap<Type>::max_heap(max_heap<Type>&& other) {
  std::swap(rep, other.rep);
}

template<typename Type>
typename max_heap<Type>::iterator
max_heap<Type>::begin() { return rep.begin(); }

template<typename Type>
typename max_heap<Type>::const_iterator
max_heap<Type>::begin() const { return rep.begin(); }

template<typename Type>
typename max_heap<Type>::const_iterator
max_heap<Type>::cbegin() const { return rep.begin(); }

template<typename Type>
typename max_heap<Type>::iterator
max_heap<Type>::end() { return rep.end(); }

template<typename Type>
typename max_heap<Type>::const_iterator
max_heap<Type>::end() const { return rep.end(); }

template<typename Type>
typename max_heap<Type>::const_iterator
max_heap<Type>::cend() const { return rep.end(); }

template<typename Type>
typename max_heap<Type>::reference
max_heap<Type>::operator=(max_heap<Type> other) {
  // copy-swap
  std::swap(rep, other.rep);
  return *this;
}

template<typename Type>
typename max_heap<Type>::reference
max_heap<Type>::operator=(max_heap<Type>&& other) {
  // copy-swap
  std::swap(rep, other.rep);
  return *this;
}

template<typename Type>
bool max_heap<Type>::operator==(const max_heap<Type>& other) {
  return std::equal(begin(), end(), other.begin(), other.end());
}

template<typename Type>
bool max_heap<Type>::operator!=(const max_heap<Type>& other) {
  return !operator==(other);
}

template<typename Type>
void max_heap<Type>::swap(max_heap<Type>& other) {
  std::swap(rep, other.rep);
}

template<typename Type>
void swap(max_heap<Type>& lhs, max_heap<Type> rhs) {
  lhs.swap(rhs);
}

template<typename Type>
typename max_heap<Type>::size_type
max_heap<Type>::size() const { return rep.size(); }

template<typename Type>
typename max_heap<Type>::size_type
max_heap<Type>::max_size() const { return rep.max_size(); }

template<typename Type>
bool max_heap<Type>::empty() const { return rep.empty(); }

template<typename Type>
void max_heap<Type>::build() {
  // skip leaf nodes  
  const auto n = begin() + std::ceil(size() / 2);
  for (auto i = n; i >= begin(); --i)
    bubble_down(i);
}

template<typename Type>
void max_heap<Type>::sort() {
  auto iter = end() - 1;

  while (iter >= begin()) {
    std::swap(*begin(), *iter);
    // bubble root down but ignore elements past iter
    bubble_down(begin(), iter);
    --iter;
  }
}

template<typename Type>
typename max_heap<Type>::reference
max_heap<Type>::maximum() { return *begin(); }

template<typename Type>
typename max_heap<Type>::const_reference
max_heap<Type>::maximum() const { return *begin(); }

template<typename Type>
void max_heap<Type>::remove(iterator elem) {
  std::swap(*elem, *(end() - 1));
  rep.resize(size() - 1);
  if (size() > 0)
    bubble_down(begin());
}

template<typename Type>
void max_heap<Type>::remove_maximum() {
  remove(begin());
}

template<typename Type>
typename max_heap<Type>::iterator
max_heap<Type>::parent_of(iterator child) {
  // parent = floor((i - 1) / 2)
  const auto idx = std::distance(begin(), child);
  return begin() + (idx - 1) / 2;
}

template<typename Type>
typename max_heap<Type>::iterator
max_heap<Type>::left_child_of(iterator parent) {
  // left_child = 2i + 1
  const auto idx = std::distance(begin(), parent);
  return begin() + (2 * idx) + 1;
}

template<typename Type>
typename max_heap<Type>::iterator
max_heap<Type>::right_child_of(iterator parent) {
  // right_child = 2i + 2
  const auto idx = std::distance(begin(), parent);
  return begin() + (2 * idx) + 2;
}

template<typename Type>
void max_heap<Type>::bubble_up(iterator elem) {
  auto child = elem;
  auto parent = parent_of(child);

  // bubble up
  while (child != parent && *child > *parent) {
    std::swap(*child, *parent);
    child = parent;
    parent = parent_of(parent);
  }
}

template<typename Type>
void max_heap<Type>::bubble_down(iterator elem) {
  bubble_down(elem, end());
}

template<typename Type>
void max_heap<Type>::bubble_down(iterator elem, iterator last) {
  auto parent = elem;
  auto left_child = left_child_of(parent);
  auto right_child = right_child_of(parent);

  // stop at last
  while (left_child < last || right_child < last) {
    // find maximum of parent, left_child, right_child
    auto max = parent;
    if (left_child < last)
      if (*max < *left_child)
        max = left_child;
    if (right_child < last)
      if (*max < *right_child)
        max = right_child;

    // max_heap property fixed
    if (parent == max) break;

    // swap with the greater child
    std::swap(*parent, *max);
    parent = max;
    left_child = left_child_of(parent);
    right_child = right_child_of(parent);
  }
}

template<typename Type>
void max_heap<Type>::insert(value_type value) {
  rep.push_back(value);
  bubble_up(end() - 1);
}

template<typename Type>
std::ostream& operator<<(std::ostream& out, const max_heap<Type>& max_heap) {
  // output contents of max_heap
  if (max_heap.size() > 0) {
    std::cout << *max_heap.begin();
    for (auto i = max_heap.begin() + 1; i < max_heap.end(); ++i)
      std::cout << ' ' << *i;
  }

  return out;
}

int main() {
  std::string line;

  // get set of integers from stdin
  do {
    std::cout << "insert set of integers: ";
    std::getline(std::cin, line);
  } while (line == "");

  // parse stdin input into vector<int>
  std::stringstream stream(line);
  std::vector<int> arr;

  while (std::getline(stream, line, ' ')) {
    try {
      const int n = std::stoi(line);
      arr.push_back(n);
    } catch (...) {
      // ignore for now
      continue;
    }
  }

  // linear time to build max_heap
  max_heap<int> h(arr.begin(), arr.end());
  std::cout << "h before: " << h << '\n';
  h.sort();
  std::cout << "h sorted: " << h << '\n';
  h.build();
  h.insert(22);
  std::cout << "h inserted: " << h << '\n';
}

EDIT: I also realized I can std::move the value into the vector in insert.

EDIT2: I realized that inside of build it should be const auto n = begin() + (size() / 2) - 1;. What is above is not strictly wrong but it may do one more bubble_down than is necessary.

\$\endgroup\$
6
\$\begingroup\$

You have a container that can store anything

template<typename Type>
class max_heap

but your underlying storage is this

std::vector<int> rep;

I'm somewhat shocked that you didn't notice this. Did you only test it on integers?


You define everything out-of-line but this makes the overall implementation quite a bit larger than it needs to be, while also making the code a little less pleasant to read. If you want to add or remove a function, you have to do it twice.

In the class, you have a forward declaration

iterator begin();

...then you have the implementation later.

template<typename Type>
typename max_heap<Type>::iterator
max_heap<Type>::begin() { return rep.begin(); }

You could just do this

iterator begin() { return rep.begin(); }

In the sort function, you have this

std::swap(*begin(), *iter);

When swapping two objects and you don't know what their type is, you should allow ADL to find custom swap functions. This pattern is very common in generic code. The standard library does this as well.

using std::swap;
swap(*begin(), *iter);

If you have a class with its own swap function like this

namespace my {

class swappable_thing {};

void swap(swappable_thing &, swappable_thing &) {
  std::cout << "Custom swap\n";
}

}

This following code does not call the custom swap function

my::swappable_thing a, b;
std::swap(a, b);

but this does

my::swappable_thing a, b;
using std::swap;
swap(a, b);

C++ has algorithms devoted to dealing with heaps. You're not using them. If there is a standard algorithm that does what you need it to do, use it. Your code becomes much simpler when you use standard algorithms.

\$\endgroup\$
  • \$\begingroup\$ I wrote the code using just ints then made it generic. I didn’t catch the vector<int> because I only tested with ints. \$\endgroup\$ – Brady Dean Nov 14 '18 at 12:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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