Maximum Heap Container

Question

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.

Answer 1

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.

• Brady Dean: I wrote the code using just ints then made it generic. I didn’t catch the vector<int> because I only tested with ints.