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}