5
\$\begingroup\$

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);
    }
}
```
\$\endgroup\$
4
  • 1
    \$\begingroup\$ Just FYI, C++ already has functions for heap manipulation. And it is not a class. A heap can be constructed over any random access container (or in fact just a range within such container), not just vector although a vector might be the natural choice. If you're reimplementing the heap for learning purpose, I suggest you familiarize yourself with the heap functions of cpp's standard library like make_heap and try to reimplement those instead. \$\endgroup\$
    – slepic
    Dec 31, 2021 at 8:35
  • 1
    \$\begingroup\$ BTW your implementation does not allow to construct a heap with N elements. You can only create empty heap and then insert N elements. Making it O(n * log(n)). But such operation can be done in O(n) and that's actually what std::make_heap function does. \$\endgroup\$
    – slepic
    Dec 31, 2021 at 8:42
  • 1
    \$\begingroup\$ @slepic It's just a trivial heap implementation. Not trying to copy the library or anything. I'm more concerned about proper c++ practices. But I do appreciate the insight, I was honestly unaware of those functions in the algorithm header. \$\endgroup\$ Dec 31, 2021 at 8:49
  • \$\begingroup\$ top might return by const reference. \$\endgroup\$
    – Jarod42
    Dec 31, 2021 at 9:55

2 Answers 2

7
\$\begingroup\$

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.

\$\endgroup\$
2
  • \$\begingroup\$ Hey thanks a lot for the feedback, I found it very valuable. I have a question about one thing though, why would I return a const reference in the top member function? Would that not return a reference to the first element in the underlying container? \$\endgroup\$ Jan 1, 2022 at 8:14
  • \$\begingroup\$ @mastmartelli Two reasons: you made the function top() const, so you cannot have it return a non-const reference to its own member variables. The second is that you don't want the caller to modify the value, because that could destroy the heap property. \$\endgroup\$
    – G. Sliepen
    Jan 1, 2022 at 9:45
3
\$\begingroup\$
  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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.