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

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
#include
#include
#include

template
class Heap
{
private:

std::vector 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& items, C compare = C()): items{items}, compare{compare} { heapify(); };
Heap(std::vector&& items, C compare = C()): items{items}, compare{compare} { heapify(); }
template
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
void Heap::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
void Heap::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
void Heap::siftUp(size_t node)
{
if (node == 0 || node >= size()) return;

const size_t p = parent(node);

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&& 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&& 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 () {  // 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.

StackExchange Code Review Q#155667, answer score: 6