C++11 (or C++14?) max heap implementation with a simple example

Question

I've been writing C++03 non-professionally for a long time, and I finally started to play around with C++11 and C++14. I decided to try my hand at implementing a data structure that I was previously unfamiliar with: a max heap.

#include <iostream>
#include <vector>
#include <string>
#include <stdexcept>

template<typename T, typename C>
class Heap
{
private:

    std::vector<T> items;
    C compare;

    // Heap operations.
    void heapify(size_t root = 0);
    void siftDown(size_t node);
    void siftUp(size_t node);

    // Utilities to retrieve parent, left, and right node indices.
    constexpr size_t parent(size_t node) const;
    constexpr size_t left(size_t parent) const;
    constexpr size_t right(size_t parent) const;

public:

    Heap(C compare = C()): compare{compare} {}
    Heap(const std::vector<T>& items, C compare = C()): items{items}, compare{compare} { heapify(); };
    Heap(std::vector<T>&& items, C compare = C()): items{items}, compare{compare} { heapify(); }
    template<typename Iterator>
    Heap(Iterator begin, Iterator end, C compare = C()): items{begin, end}, compare{compare} { heapify(); };
    Heap(const Heap&) = default;
    Heap(Heap&&) = default;
    ~Heap() = default;
    Heap& operator=(const Heap&) = default;
    Heap& operator=(Heap&&) = default;

    void push(const T& item);
    T pop();
    const T& top() const;

    const T& item(size_t node) const;
    constexpr size_t size() const;
};

// Heapify an unordered array in O(N). This can also be done in O(N log N) using repeated insertions.
template<typename T, typename C>
void Heap<T, C>::heapify(size_t root)
{
    if (root >= size()) return;

    size_t l = left(root), r = right(root);

    heapify(l);
    heapify(r);

    siftDown(root);
}

// Sift an item down in O(log N).
template<typename T, typename C>
void Heap<T, C>::siftDown(size_t node)
{
    size_t l = left(node), r = right(node);

    // Find which item should be highest between this one and its children.
    size_t higher = node;
    if (l < size() && compare(items[l], items[higher])) higher = l;
    if (r < size() && compare(items[r], items[higher])) higher = r;

    // If one of its children should be higher, swap and continue to sift down.
    if (higher != node)
    {
        std::swap(items[node], items[higher]);
        siftDown(higher);
    }
}

// Sift an item up in O(log N).
template<typename T, typename C>
void Heap<T, C>::siftUp(size_t node)
{
    if (node == 0 || node >= size()) return;

    const size_t p = parent(node);

    // If this item should be higher than its parent, swap and continue to sift up.
    if (compare(items[node], items[p]))
    {
        std::swap(items[node], items[p]);
        siftUp(p);
    }
}

template<typename T, typename C>
constexpr size_t Heap<T, C>::parent(size_t node) const
{
    return node > 0 ? (node - 1) / 2 : node;
}

template<typename T, typename C>
constexpr size_t Heap<T, C>::left(size_t parent) const
{
    return parent * 2 + 1;
}

template<typename T, typename C>
constexpr size_t Heap<T, C>::right(size_t parent) const
{
    return parent * 2 + 2;
}

template<typename T, typename C>
void Heap<T, C>::push(const T& item)
{
    // Insert as the last item.
    items.push_back(item);

    // Sift it up to re-establish heap property.
    siftUp(size() - 1);
}

template<typename T, typename C>
T Heap<T, C>::pop()
{
    if (size() == 0) return T();

    T ret{top()};

    // Move last item to the top, then reduce the array size by one.
    items[0] = items[size() - 1];
    items.pop_back();

    // Sift this new top item down to re-establish heap property.
    siftDown(0);

    return ret;
}

template<typename T, typename C>
const T& Heap<T, C>::top() const
{
    return items.front();
}

template<typename T, typename C>
const T& Heap<T, C>::item(size_t node) const
{
    return items[node];
}

template<typename T, typename C>
constexpr size_t Heap<T, C>::size() const
{
    return items.size();
}

template<typename T, typename C>
void print(std::ostream& stream, const Heap<T, C>& h, size_t root = 0, size_t level = 0)
{
    if (root >= h.size()) return;

    // Print left child.
    print(stream, h, root * 2 + 1, level + 1);

    stream << std::string(level * 4, ' ') << h.item(root) << "\n";

    // Print right child.
    print(stream, h, root * 2 + 2, level + 1);
}

template<typename T, typename C>
std::ostream& operator<<(std::ostream& stream, const Heap<T, C>& h)
{
    print(stream, h);
    return stream;
}

int main()
{
    Heap<int, std::greater<int>> h;
    std::vector<int> arr;

    for (int i = 0; i < 10; ++i)
    {
        int x = rand() % 20;
        h.push(x);
        arr.push_back(x);
    }

    Heap<int, std::greater<int>> h2{arr.begin(), arr.end()};

    std::cout << "Created via push():\n" << h;
    std::cout << "Created via heapify():\n" << h2;

    std::cout << "Popping top item..." << std::endl;

    h.pop();
    h2.pop();

    std::cout << "Created via push():\n" << h;
    std::cout << "Created via heapify():\n" << h2;
}

Mainly looking for feedback on:

• Am I using C++11/14 features correctly? Have I written anything that's redundant? Am I missing anything important?
• Is my max heap implementation correct? Is my time complexity analysis (see comments above implementations) correct?
• Have I followed best practices in implementing a generic container with a custom comparison function?
• Have I made any mistakes with regards to exception safety?

Aside from that, please feel free to completely rip the code apart. Give me your honest thoughts as if you're reviewing a coworker's checkin (and ignore the fact that if I was your coworker, I would just use std::priority_queue instead).

Answer 1

Move constructor

Common mistake here. You would think that items would be an R-Value reference; but its not. Remember "named" objects are never R-Value references the && just marks the binding site for an R-Value reference.

    Heap(std::vector<T>&& items, C compare = C())
        : items{items}     // This will bind to the std::vector(std::vector const&)
        , compare{compare}
    { heapify(); }

When you pass this value to "items" you need to create the R-Value reference again.

    Heap(std::vector<T>&& items, C compare = C())
        : items{std::move(items)}     // This will bind to the std::vector(std::vector&&)
        , compare{compare}
    { heapify(); }

You have the move constructor. So why do you only have a copy push?

    void push(const T& item);

I would expect a move push.

    void push(T&& item); 

The standard containers (that support pop()) return a void type. This is because there is not a way to implement an exception safe pop() that returns a value. That is also why they have top(). So you can get the value with top(). Then do an exception safe pop().

    T pop();
    const T& top() const;

So I would define the interface like this:

    void pop();
    const T& top() const;

If you are providing a generic accesser:

    const T& item(size_t node) const;

Then why not provide operator[](size_t node)? Not sure it is a good idea. but it is a question you should ask and answer for yourself.

Style

Check your local style guide. I personally don't like this as I think it makes the if statement harder to read. But your guide may allow it.

    if (root >= size()) return;

I would like to have seen:

    if (<cont>) {  // Always put braces on if statements.
        return;    // Always new line and indent for the sub block.
    }

One Line per declaration;

    size_t l = left(root), r = right(root);

The code is suposed to be human readable. Prefer to put one declaration per line. It makes the code easier to read and parse for a maintainer.

Also prefer to use meaningful identifier names. If you do a search for l or r then you are going to get a lot of false positives when searching your code (especially if your code has comments).

    size_t leftIndex  = left(root);  // Not that hard.
    size_t rightIndex = right(root); // easier to search for.

Questions from comments:

1) Should I just use auto everywhere, like const auto leftIndex = ...? What about const for everything that doesn't change?

I don't think so. The main thing about C++ is its strong typing. But you also need to worry about the compilers ability to change types (compiler inserted casts (float => int etc), or use of single argument constructor to convert).

Personally I use specific types wherever I need a specific type; but I use auto when I don't care about the type (Iterators are a great example here; I don't care about the actual type I care about the behavior).

2) Should I use move semantics for compare in the constructors?

I don't think so. You compare type should be relatively light weight (in fact I doubt there are many use cases where the care object has any members).

3) Do I even need std::vector&& items in the constructor? Why not just std::vector items, let the std::vector constructor do a move for the Heap<...> foo{std::move(existingItems)} call, and then use std::move again inside the Heap constructor?

You are correct. You could have a normal parameter.

Questions from above:

Mainly looking for feedback on:

Am I using C++11/14 features correctly? Have I written anything that's redundant? Am I missing anything important?

Apart from you mistake with the move construction of the input vector it looks fine.

Is my max heap implementation correct? Is my time complexity analysis (see comments above implementations) correct?

Looks OK.

Have I followed best practices in implementing a generic container with a custom comparison function?

Not really. You are missing a whole bunch of functionality if you wish to call this a container. See: Concept: Container. BUT I don't think you need to call your structure a container it is a Container Adapter just like a std::priority_queue

Have I made any mistakes with regards to exception safety?

Since you don't do any resource management (and delegate all the work to std::vector) you are probably fine.

Answer 2

Regarding "best practices", I'd recommend checking out the C++ Core Guidelines for suggestions like:

• "If your function may not throw, declare it noexcept". This seems like especially applicable advice for library code.
• "Use const to define objects with values that do not change after construction". I noticed that variables like l in Heap<T, C>::heapify(size_t root) wasn't doing this.
• "Use auto to avoid redundant repetition of type names". auto also requires variables to be initialized which may prevent a coder who is changing your code from accidentally forgetting to initialize a value. It's usage also seems helpful for template code where the types may be more fluid to begin with and I noticed that the l variable is always declared as type size_t (instead of 'auto' or 'const auto').

Regarding missing anything important:

• Perhaps the hypothetical situation of when std::numeric_limits<size_t>::max() / 2 items have been pushed into your container. Assuming memory hadn't been exhausted before then, it looks like you'd be getting mod wrap semantics at this point. Both the parent * 2 + 1 or parent * 2 + 2 operations would wrap around and I suspect siftDown would have a problem. If nothing else, it seems reasonable to document this limitation (assuming I'm correct).