A heap implementation in C++

heap.cpp

#include <iostream>
#include <vector>
#include <algorithm>
#include <cassert>

template <typename T>
void swap(T& vec, std::size_t a, std::size_t b);

constexpr std::size_t firstChild(std::size_t i);

constexpr std::pair<bool, std::size_t> parent(std::size_t i);

template <typename T>
class Heap {
public:
    Heap() {}

    // O(N lg(N))
    explicit Heap(std::vector<T> v) {
        std::for_each(begin(v), end(v), [this] (T val) { insert(val); });
    }

    // O(N lg(N))
    explicit Heap(std::initializer_list<T> c) { 
        std::for_each(begin(c), end(c), [this] (T val) { insert(val); });
    }

    virtual ~Heap() {}

    // O(lg(N))
    void insert(T val) {
        heap_.push_back(val);
        bubbleUp(heap_.size()-1);
    }

    // Constant time
    T peek() const {
        assert(!empty());

        return heap_[0];
    }

    // Constant time
    bool empty() const { return heap_.size() == 0; }

    // O(lg(N))
    T extractMin() {
        assert(!empty());

        const auto result = heap_[0];
        heap_[0] = heap_.back();
        heap_.pop_back();
        bubbleDown(0);
        return result;
    }

private:
    std::vector<T> heap_;

    // O(lg(N))
    void bubbleUp(std::size_t i) {
        const auto result = parent(i);
        if (!result.first) {
            return;
        }
        if (heap_[result.second] > heap_[i]) {
            swap(heap_, result.second, i);
            bubbleUp(result.second);
        }
    }

    // O(lg(N))
    void bubbleDown(std::size_t i) {
        const auto child = firstChild(i);
        auto minIndex = i;
        for (std::size_t n = 0; n < 2; ++n) {
            if (child+n < heap_.size()) {
                if (heap_[minIndex] > heap_[child+n]) {
                    minIndex = child+n;
                }
            }
        }
        if (minIndex != i) {
            swap(heap_, i, minIndex);
            bubbleDown(minIndex);
        }
    }
};

// Constant time
// Consider using std::optional instead of std::pair in C++17.
constexpr std::pair<bool, std::size_t> parent(std::size_t i) {
    if (i == 0) {
        return { false, 0 };
    }
    return { true, (i - 1) / 2 };
}

// Constant time
constexpr std::size_t firstChild(std::size_t i) {
    return (2 * i) + 1;
}

template <typename T>
void swap(T& vec, std::size_t a, std::size_t b) {
    const auto temp = vec[a];
    vec[a] = vec[b];
    vec[b] = temp;
}

// Worst case runtime: O(N lg(N))
template <typename T>
void heapsort(std::vector<T>& v) {
    Heap<T> heap(v);
    for (std::size_t i = 0; i < v.size(); ++i) {
        v[i] = heap.extractMin();
    }
}

int main() {
    std::vector<int> v{5,4,6,3,7,2,8,1,9};
    assert(!std::is_sorted(begin(v), end(v)));
    heapsort(v);
    assert(std::is_sorted(begin(v), end(v)));
}