Binary Heap Structure Class C++

Question

I wrote a binary heap structure class in C++. It is a templated class with a comparison type as one of the template parameters to allow for a min or max heap.

I have not written anything in C++ in a bit and I am primarily looking for feedback on whether I am using obsolete practices, generally incorrectly using try/throw/catch, missed opportunity on qualifiers/tags, or anything of the sort. Any feedback pertinent to general C++ usage and the specific heap structure implementation would be amazing. Thank you in advance.

#pragma once

#include <functional>
#include <iostream>
#include <stdexcept>
#include <vector>

template <typename T, typename C=std::greater<T>> // by default a max heap
class Heap
{
public:
    Heap() = default;
    ~Heap() = default;
    void insert(T value);
    T top() const;
    void remove_top();
    template <typename _T, typename _C>
    friend std::ostream& operator<<(std::ostream &cout, const Heap<_T, _C> &_heap);
private:
    void switch_elements(size_t index1, size_t index2);
    void sift_down(size_t index);
    void sift_up(size_t index);
    std::vector<T> container;
};

template <typename T, typename C>
void Heap<T, C>::insert(T value)
{
    container.push_back(value);
    sift_up(container.size() - 1);
}

template <typename T, typename C>
T Heap<T, C>::top() const
{
    try
    {
        if (container.empty())
            throw std::out_of_range("ERROR: The heap is empty!");
    }
    catch (const std::out_of_range &err)
    {
        std::cerr << err.what() << '\n';
    }
    
    return container[0];
}

template <typename T, typename C>
void Heap<T, C>::remove_top()
{
    try
    {
        if (container.empty())
            throw std::out_of_range("ERROR: The heap is empty! Cannot remove an element.");
    }
    catch (const std::out_of_range &err)
    {
        std::cerr << err.what() << '\n';
    }
    
    container.front() = container.back();
    container.pop_back();
    if (!container.empty())
        sift_down(0);
}

template <typename T, typename C>
std::ostream& operator<<(std::ostream &cout, const Heap<T, C> &_heap)
{
    for (const T &elem : _heap.container)
        cout << elem << ' ';
    
    return cout;
}

template <typename T, typename C>
void Heap<T, C>::switch_elements(size_t index1, size_t index2)
{
    T temp = container[index1];
    container[index1] = container[index2];
    container[index2] = temp;
}

template <typename T, typename C>
void Heap<T, C>::sift_down(size_t index)
{
    C compare;
    size_t left_child_index = index * 2 + 1;
    size_t right_child_index = index * 2 + 2;
    size_t target_index = index;
    
    if (left_child_index < container.size() && compare(container[left_child_index], container[target_index]))
        target_index = left_child_index;
    
    if (right_child_index < container.size() && compare(container[right_child_index], container[target_index]))
        target_index = right_child_index;
    
    if (index != target_index)
    {
        switch_elements(target_index, index);
        sift_down(target_index);
    }
}

template <typename T, typename C>
void Heap<T, C>::sift_up(size_t index)
{
    if (index == 0)
        return;
    
    C compare;
    size_t parent_index = (index - 1) / 2;
    
    if (compare(container[index], container[parent_index]))
    {
        switch_elements(index, parent_index);
        sift_up(parent_index);
    }
}
```

Answer 1

Consider using the standard library's heap functions

As slepic already mentioned, C++ has functions to manipulate heaps. However, these are just free functions that manipulate other containers, and nothing prevents you from destroying the heap property. So implementing your own heap class that strictly enforces the heap property might be beneficial. Still, you can use standard library functions inside your class's member functions, like std::push_heap().

Of course, ignore this advice if you want to practice implementing heap manipulating algorithms yourself.

Avoid declaring constructors/destructors unnecessarily

You don't have to declare the constructor and destructor if they don't do anything, not even using = default. See the rule of zero.

Consider following the naming conventions of STL containers

While some of your member function names match those of the STL containers, remove_top() does not. Consider giving your class the same interface as std::stack(), so push() instead of insert(), and pop() instead remove_top(). Also consider adding an emplace() function to allow pushing a new element with potentially less copying:

template<typename... Args>
void emplace(Args&&... args) {
    container.emplace_back(std::forward<Args>(args)...);
    sift_up(container.size() - 1);
}

Pass values by reference where appropriate

Your insert() function takes its parameter by value, which means a copy will be made. Similarly, your top() returns by value, which also makes a copy. Make those functions pass by const reference instead:

void push(const T& value);
const T& top() const;

You don't have to change anything in the body of those functions. If you look at std::stack::push(), you'll notice it has two forms; one takes a const reference, the other takes an r-value reference. The latter makes it possible to efficiently move values into your container. Consider adding that overload as well:

void push(T&& value) {
    container.push_back(std::move(value));
    sift_up(container.size() - 1);
}

Remove the operator<<()

I recommend that you remove the operator<<() function. The reason is that it is very likely that it will not do what the caller wants. There are many ways to format a list of items; space separated is just one, but someone might want comma separated, or every entry on one line. Also consider that the output is ambiguous if individual elements, when printed, might contain spaces (consider a Heap<std::string> for example). Also consider that you are printing things in the order in which they appear in the container, when the caller might want to see the elements in sorted order.

Just remove this responsibility from your class, and leave it up to the caller to format the output.

Write std::size_t instead of size_t

The C++ standard defines size_t to be inside the std namespace. Don't rely on bare size_t working, as this is implementation defined behavior.

Use std::swap()

You don't need to write your own switch_elements(), std::swap() can easily swap two elements of a container. For example:

std::swap(container[target_index], container[index]);

Allow the comparator function to be specified in the constructor

Merely storing the type of the comparator as a template parameter is not enough to allow all possible types of comparator functions to be used. Consider passing a lambda function with captures:

auto compare = [i = 3](int& a, int& b){ return a + i < b; }
Heap<int, decltype(compare)> heap; // lambda closure type has a deleted default constructor

You should allow the comparator to be specified in the constructor:

template <typename T, typename C = std::greater<T>>
class Heap
{
    C compare;
public:
    Heap(const C& compare = C()): compare(compare) {}
    ...
};

Now the above lambda can be passed as the comparator function like so:

Heap<int, decltype(compare)> heap(compare);

Don't catch your own exceptions

Your functions that throw also catch their own exceptions, causing an error to be written to std::cerr, but then dereferencing the out-of-range element still happens, leading to undefined behavior. Don't catch your own exceptions, let the caller handle them if so desired.

Answer 2

1. Don't use unnecessary headers. The final set of headers after removal are:

   #include <iostream>
   #include <vector>
   

2. In a general way, whenever we take out something from a data structure, we call it popping, I would suggest using the same nomenclature here.

   void pop();
   

3. Also, sift seems to mean passing something through a sieve, I think you meant:

    void shift_down(size_t index);
    void shift_up(size_t index);
   

4. Again, a nomenclature thing: container in C++ especially STL could mean any of list,stack,queue, I would name it as simply heapArray may be.

   std::vector<T> heapArray;
   

5. Reiterating this. Don't swallow exceptions; this is not a trivial thing but a logical error. How does the caller even know the exception has occurred ?

6. This function is totally unnecessary; one can use std::swap() here.

   template <typename T, typename C>
   void Heap<T, C>::switch_elements(size_t index1, size_t index2)
   {
   
       T temp = container[index1];
       container[index1] = container[index2];
       container[index2] = temp;
   }
   

   Just call

   std::swap(container[index1],container[index2]);
   

7. I don't quite like the idea of having a friend method for printing. It kills encapsulation; you are giving the caller a sneak peak into the way you want to store the elements. Let them do the hard work by calling the top and popping out to print out the elements. This is more so in case of a heap, where the only guarantee you get is that top will be greatest or smallest. Add this to reasons the previous reviewer mentioned.