C++11 min-heap with configurable arity

Question

Here is a simple heap implementation that allows the heap arity to be chosen at compile time, including the degenerate case where n=1 and the heap is effectively a sorted array with a terrible repair strategy.

The heap implementation class, broadly speaking, has two repair strategies: making swaps in the direction of the leaves and making swaps in the direction of the root.

The prototypical use case for a leafward_heapify is when we construct a new heap from a vector. In that case, we start iterating over indices backwards (which starts at the leaves) and swap big items down (aka a leafward_heapify).

heapify_rootward is used when we insert a new item of unknown size at the bottom right corner of the heap.

This heap is not thread-safe and is not meant to be thread-safe.

The heap-class is meant to be the public-facing API.

The detail::heap_impl heap does all the work, but its API isn't bounds-checked when NDEBUG is defined, it doesn't have any const methods, and its methods and members are all public.

The heap class does have const and non-const versions of each const method.

My main concern is that I've done a lot of things that are weird or non-idiomatic and I'd like to know how rewrite this code to be less weird.

Also, I've tried to make sure that I'm only taking copies of small, trivially copyable things, except where it's unavoidable (such as the constructor taking a std::vector) and have tried to implement things on top of swap as much as possible, but I'm not sure that's a good idea.

#ifndef DARY_HEAP_HPP
#define DARY_HEAP_HPP 1

#include <algorithm>
#include <exception>
#include <utility>
#include <vector>

namespace dary_heap {

using std::vector;

namespace detail {

template <class T, int ARITY> class heap_impl {
public:
  static_assert(ARITY > 0, "ARITY must be at least 1");
  vector<T> storage;
  using ssize_type = std::ptrdiff_t;
  using iterator = decltype(storage.begin());
  using const_iterator = decltype(storage.cbegin());

  heap_impl() noexcept = default;
  heap_impl(heap_impl &&) noexcept = default;

  heap_impl(std::vector<T> vs) {
    swap(vs, storage);
    for (auto i = -1 + ssize(); i >= 0; i--) {
      heapify_leafwards(i);
    }
  }

  constexpr ssize_type ssize() const noexcept {
    return static_cast<ssize_type>(storage.size());
  }

  constexpr ssize_type last() const noexcept { return ssize() - 1; }

  constexpr ssize_type first() const noexcept { return 0; }

  T get(ssize_type i) noexcept {
    assert(i < ssize());
    assert(i >= 0);
    return storage[i];
  }

  std::pair<bool, ssize_type> get_parent(ssize_type i) {
    if (i == 0) {
      return {false, 0};
    }
    auto idx = i;
    idx -= 1;
    idx /= ARITY;
    assert(idx < i);
    return {true, idx};
  }

  std::pair<bool, ssize_type> get_first_child(ssize_type i) {
    auto idx = i;
    idx *= ARITY;
    idx += 1;
    if (idx >= ssize()) {
      return {false, 0};
    }
    return {true, idx};
  }

  std::pair<bool, ssize_type> get_last_child(ssize_type i) {
    auto p = get_first_child(i);
    if (!p.first) {
      return {false, 0};
    }
    auto idx = p.second + ARITY - 1;
    return {true, std::min<decltype(idx)>(idx, last())};
  }

  void swap_indices(ssize_type i, ssize_type j) {
    assert(i >= 0);
    assert(i < ssize());
    assert(j >= 0);
    assert(j <= ssize());
    iter_swap(storage.begin() + i, storage.begin() + j);
    return;
  }

  std::pair<bool, ssize_type> get_smallest_child(ssize_type i) {
    auto p1 = get_first_child(i);
    if (!p1.first) {
      return {false, 0};
    }
    auto start = p1.second;
    auto stop = get_last_child(i).second;
    assert(start <= stop);
    ssize_type argmin = start;
    for (auto jj = start + 1; jj <= stop; jj++) {
      if (storage[jj] < storage[argmin]) {
        argmin = jj;
      }
    }
    assert(argmin > i);
    assert(argmin < ssize());
    return {true, argmin};
  }

  void push_back(T u) noexcept(false) {
    storage.push_back(u);
    heapify_rootwards(last());
    return;
  }

  T at(ssize_type i) noexcept(false) {
    if (i < 0) {
      throw std::runtime_error("index cannot be negative");
    }
    if (i >= ssize()) {
      throw std::runtime_error("index out of bounds");
    }
    return storage[i];
  }

  // when we are given an initially not-in-heap-order
  // std::vector, we need to potentially make swaps
  // to enforce the heap invariant.
  // under the assumption that our child subheaps are all min-heaps
  // we swap with the smallest child and then check the location
  // that we just swapped into.
  std::pair<bool, ssize_type> heapify_leafwards_step(ssize_type i) {
    auto p = get_smallest_child(i);
    if (!p.first) {
      return {false, 0};
    }
    auto smallest = p.second;
    if (storage[smallest] < storage[i]) {
      swap_indices(smallest, i);
      return {true, smallest};
    } else {
      return {false, 0};
    }
  }

  void heapify_leafwards(ssize_type i) {
    auto cur = i;
    while (true) {
      auto p = heapify_leafwards_step(cur);
      if (!p.first) {
        return;
      } else {
        assert(p.second > cur);
        cur = p.second;
      }
    }
  }

  // when we have a heap that is completely in heap order except
  // for a single item (because it was inserted, for instance).
  // we repair the heap by
  std::pair<bool, ssize_type> heapify_rootwards_step(ssize_type i) {
    auto p = get_parent(i);
    if (!p.first) {
      return {false, 0};
    }
    auto root_i = p.second;
    assert(i > 0);
    assert(root_i < i);
    if (storage[i] < storage[root_i]) {
      swap_indices(i, root_i);
      return {true, root_i};
    }
    return {false, 0};
  }

  void heapify_rootwards(ssize_type i) {
    ssize_type cur = i;
    while (true) {
      auto p = heapify_rootwards_step(cur);
      if (!p.first) {
        return;
      } else {
        assert(p.second < cur);
        cur = p.second;
      }
    }
  }

  // always succeeds!
  void remove_last() noexcept {
    auto usize = storage.size();
    if (usize != 0) {
      storage.resize(usize - 1);
    }
  }

  void remove(ssize_type i) noexcept {
    assert(i >= 0);
    assert(i < ssize());
    swap_indices(i, last());
    remove_last();
    // if the item is the biggest in the heap
    // we need to push it into the leaves.
    // in pathological cases where the last item
    // happens to be relatively small, we also heapify
    // towards the root.
    heapify_leafwards(i);
    heapify_rootwards(i);
  }

  iterator begin() noexcept { return storage.begin(); }

  iterator end() noexcept { return storage.end(); }

  const_iterator cbegin() noexcept { return storage.cbegin(); }

  const_iterator cend() noexcept { return storage.cend(); }
};

} // namespace detail

template <class T, int ARITY> class heap {
private:
  mutable detail::heap_impl<T, ARITY> impl;

public:
  using ssize_type = typename decltype(impl)::ssize_type;
  using iterator = typename decltype(impl)::iterator;
  ;
  using const_iterator = typename decltype(impl)::const_iterator;

  heap() noexcept = default;
  heap(heap &&) noexcept = default;

  heap(std::vector<T> v) : impl(v) {}

  void push_back(T u) noexcept(false) { impl.push_back(u); }

  T at(ssize_type i) noexcept(false) { return impl.at(i); }

  T at(ssize_type i) const noexcept(false) { return impl.at(i); }

  constexpr ssize_type ssize() const noexcept { return impl.ssize(); }

  void remove(ssize_type i) noexcept(false) {
    if (i < 0) {
      throw std::runtime_error("index cannot be negative");
    }
    if (i >= ssize()) {
      throw std::runtime_error("index too large");
    }
    impl.remove(i);
  }

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

  iterator end() { return impl.end(); }

  const_iterator cbegin() { return impl.cbegin(); }

  const_iterator cbegin() const { return impl.cbegin(); }

  const_iterator cend() { return impl.cend(); }

  const_iterator cend() const { return impl.cend(); }
};

} // namespace dary_heap

#endif // DARY_HEAP_HPP

And here's the test code, just called dary_heap.cpp.

#define BOOST_TEST_MAIN 1
#define BOOST_TEST_DYN_LINK 1
#define BOOST_TEST_MODULE dary_heap
#include <boost/test/unit_test.hpp>

#include "dary_heap.hpp"
#include <cstdio>

BOOST_AUTO_TEST_SUITE(heap)

BOOST_AUTO_TEST_CASE(empty_heap) {
  using namespace dary_heap;
  heap<float, 4> h;
  const heap<float, 4> &c_h = h;
  BOOST_CHECK(h.ssize() == 0);
  BOOST_CHECK(h.begin() == h.end());
  BOOST_CHECK(h.cbegin() == h.cend());
  BOOST_CHECK(c_h.cbegin() == c_h.cend());
  BOOST_CHECK_THROW(h.at(0), std::runtime_error);
}

BOOST_AUTO_TEST_CASE(singleton_heap) {
  using namespace dary_heap;
  heap<float, 4> h;
  const heap<float, 4> &c_h = h;
  h.push_back(7.0f);
  BOOST_CHECK(h.ssize() == 1);
  BOOST_CHECK(1 + h.begin() == h.end());
  BOOST_CHECK(1 + h.cbegin() == h.cend());
  BOOST_CHECK(1 + c_h.cbegin() == c_h.cend());
  BOOST_CHECK(h.at(0) == 7.0f);
  BOOST_CHECK_THROW(h.at(1), std::runtime_error);
}

BOOST_AUTO_TEST_CASE(singleton_heap_from_vector) {
  using namespace dary_heap;
  std::vector<float> v{7.0f};
  heap<float, 4> h(v);
  const heap<float, 4> &c_h = h;
  BOOST_CHECK(h.ssize() == 1);
  BOOST_CHECK(1 + h.begin() == h.end());
  BOOST_CHECK(1 + h.cbegin() == h.cend());
  BOOST_CHECK(1 + c_h.cbegin() == c_h.cend());
  BOOST_CHECK(h.at(0) == 7.0f);
  BOOST_CHECK_THROW(h.at(1), std::runtime_error);
}

BOOST_AUTO_TEST_CASE(two_element_heap) {
  using namespace dary_heap;
  heap<float, 4> h;
  // push elements in the "wrong" order
  h.push_back(7.0f);
  h.push_back(1.0f);
  BOOST_CHECK(h.at(0) == 1.0f);
  BOOST_CHECK(h.at(1) == 7.0f);
  BOOST_CHECK(h.ssize() == 2);
}

BOOST_AUTO_TEST_CASE(binary_heap_remove_min) {
  using namespace dary_heap;
  heap<float, 2> h;
  h.push_back(4.0f);
  h.push_back(7.0f);
  h.push_back(8.0f);
  BOOST_CHECK(h.at(0) == 4.0f);
  BOOST_CHECK(h.at(1) == 7.0f);
  BOOST_CHECK(h.at(2) == 8.0f);
  BOOST_CHECK_NO_THROW(h.remove(0));
  BOOST_CHECK(h.at(0) == 7.0f);
  BOOST_CHECK(h.at(1) == 8.0f);
  BOOST_CHECK_THROW(h.at(2), std::runtime_error);
}

BOOST_AUTO_TEST_CASE(unary_heap_remove_middle) {
  using namespace dary_heap;
  std::vector<int> v{0, 1, 2, 3, 4, 5, 6, 7};
  heap<int, 1> h(v);
  BOOST_CHECK(h.at(0) == 0);
  BOOST_CHECK(h.at(1) == 1);
  BOOST_CHECK(h.at(2) == 2);
  BOOST_CHECK(h.at(3) == 3);
  BOOST_CHECK(h.at(4) == 4);
  BOOST_CHECK(h.at(5) == 5);
  BOOST_CHECK(h.at(6) == 6);
  BOOST_CHECK(h.at(7) == 7);
  h.remove(3);
  BOOST_CHECK(h.at(0) == 0);
  BOOST_CHECK(h.at(1) == 1);
  BOOST_CHECK(h.at(2) == 2);
  BOOST_CHECK(h.at(3) == 4);
  BOOST_CHECK(h.at(4) == 5);
  BOOST_CHECK(h.at(5) == 6);
  BOOST_CHECK(h.at(6) == 7);
  BOOST_CHECK_THROW(h.at(7), std::runtime_error);
}

BOOST_AUTO_TEST_SUITE_END()

Since there are only two files, a shell script suffices for the build:

#!/bin/sh

PROGNAME=program.exe

LIBS=
LIBS+="-lboost_unit_test_framework"

${CXX:-clang++} -o "${PROGNAME:-x}" *.cpp -I. -std=c++11 "$@" ${LIBS}

Answer 1

First, thumbs-up for providing a test suit, although I couldn't make it work (copy-and-paste on wandbox, it might be the reason why).

Now on to the not so good:

• Your code is quite long; the longer it is, the harder it is to read. That's why you must always try to be as concise as possible. In this case I strongly believe that you could have cut out a lot. It isn't even hard to do: let me give you a very trivial example:

Ex:

// original code
auto idx = i;
idx *= ARITY;
idx += 1;
if (idx >= ssize()) {
  return {false, 0};
}
return {true, idx};

// concise version:
auto index = i * ARITY + 1;
return index < ssize() ? { true, index } : { false, 0 };

// or with C++17, localized variable
if (auto index = i * ARITY + 1; index < ssize())
     return { true, index };
else return { false, 0 };

• Your code is cluttered with variables that have short, more or less obscure or arbitrary names (i, j, jj, vs, etc.). Variable names introduce meaning, it's a great way to document your code and make it easier to read and understand:

Ex (continued):

// now we know what it is the index of
if (auto child_index = parent_index * ARITY + 1; child_index < ssize())
     return { true, child_index };
else return { false, 0 };

• Another reason why your code is too long for what it does is that it is overly defensive. I assume you thought that asserts are free because they can be toggled off. But they're not because it can obscure your error-handling strategy: why are there asserts in some places, if clauses in others, or even exceptions? I can't give you a hard rule about this, but generally it's good to check the error as locally as possible, and handle it as centrally as possible. It's not good to do it everywhere.

• Your "signed size" gymnastic is dangerous. I understand where it comes from, but look where it goes to:

How dangerous is:

constexpr ssize_type ssize() const noexcept {
    return static_cast<ssize_type>(storage.size());
}

Well, tell me what happens if storage.size() is greater than std::numeric_limits<ssize_type>::max()? Well, you've got a negative size (I don't consider the theoretically possible case where the overflow could lead to a positive but false size -> good luck finding the bug). And your code full of asserts doesn't even check this!!

• returning a std::pair<bool, index> is a bit cumbersome. Depending on the version of C++ you can use, you can return a std::optional or simply an iterator (when an iterator points past the last element, it indicates failure). NB: if you have access to C++17, structured bindings make for a more elegant syntax when assigning a pair: auto [success, child_index] = get_smallest_child(parent_index);

• the distinction between the implementation and the "front" class is weird. What did you want to achieve with this? If it's about re-compilation and the "pimpl idiom", then you need to use a pointer to heap_impl inside heap. A pointer allows you to refer to an incomplete type, and define the type somewhere else.

• do you really want to provide random access to the elements of your heap? There might be scenarios where you need this (or are there? heaps aren't completely sorted, the children of a given parent can be in any order, so why would you get the 3rd, and not the 2nd or the 4th?), but you generally use heaps as a kind of priority queue. You only need to provide access to the "top" element. It will simplify your code and get you closer to the principle: make an interface that is easy to use and hard to misuse (out of bond access is harder this way).

• your noexcept policy is incoherent and a bit tedious also. You tag almost everything but not begin() or end(), for some reason. noexcept(false) isn't really necessary, in the sense that no one (neither compiler nor client) will expect to be protected from exceptions unless there's a noexcept tag at the end of the signature.

• I think you should have offered to customize the comparison operator. It's really useful when the element doesn't provide a comparison operator, of if you want to compare the elements in a different order, or a projection of the elements.

• there are probably other little things that can be improved, but I feel like they'll become more obvious when you work further on the initial code. With that in mind, here's a quick, more modern, iterator based implementation of a heap to give you a comparison point and some hints:

Ex:

#include <vector>
#include <functional>
#include <optional>
#include <iostream>

template <typename T, typename Pred = std::less<T>, std::size_t ARITY = 2>
class heap {

    using Iterator = std::vector<T>::iterator;

    public: std::vector<T> storage; private: // for testing purpose
    Iterator root = storage.begin();
    Iterator last_element = root;

    Pred predicate;

    Iterator get_parent(Iterator child) {
        const auto parent_index = (std::distance(root, child) - 1) / ARITY;
        return std::next(root, parent_index);
    }

    std::pair<Iterator, Iterator> get_children(Iterator parent) {
        const auto children_index = std::distance(root, parent) * ARITY + 1;
        if (children_index >= storage.size()) return { last_element, last_element };
        const auto children_number = std::min(storage.size() - children_index, ARITY);
        return { std::next(root, children_index), std::next(root, children_index + children_number) };
    }

    void restore_up(Iterator child);
    void restore_down(Iterator parent);

    public:

    heap() = default;

    template <typename Iter>
    heap(Iter first, Iter last);

    std::optional<T> pop() { // simplification. You need to provide both T top() and void pop() to be exception safe
        if (storage.empty()) return {};
        auto result = std::exchange(*root, *last_element--);
        storage.pop_back();
        restore_down(root);
        return result;
    }

};

template <typename T, typename Pred, std::size_t ARITY>
void heap<T, Pred, ARITY>::restore_up(Iterator child) {
    while (child != root) {
        auto parent = get_parent(child);
        if (!predicate(*child, *parent)) return;
        std::iter_swap(child, parent);
        child = parent;
    }
}

template <typename T, typename Pred, std::size_t ARITY>
void heap<T, Pred, ARITY>::restore_down(Iterator parent) {
    while (true) {
        auto [first, last] = get_children(parent);
        if (first == last) return;
        auto top_child = std::min_element(first, last, predicate);
        if (!predicate(*top_child, *parent)) return;
        std::iter_swap(top_child, parent);
        parent = top_child;
    }
}

template <typename T, typename Pred, std::size_t ARITY>
template <typename Iter>
heap<T, Pred, ARITY>::heap(Iter first, Iter last) 
    : storage(first, last) {
        if (first == last) return;
        last_element = std::prev(storage.end());
        auto last_parent = get_parent(last_element);
        do {
            restore_down(last_parent);
        } while (last_parent-- != root);
}

int main() {
    std::vector<int> data {3,5,7,9,4,1,6,8};
    heap<int, std::greater<int>> test(data.begin(), data.end());
    for (auto i : test.storage) std::cout << i << ' ';
}