Binary heap performance optimization

I have implemented a binary heap as a exercise in data structures. I realize that I'm missing some useful functions (increase/decrease key for example) but I don't consider them interesting for the exercise.

I'm interested in learning if there is anything that I could do to improve performance of the pop operation which by my benchmarks is the slowest operation. I have already taken it down from the initial 6.5s to 2.5s on my machine.

Compiling and running the below on my machine yields:


g++ -O3 --std=c++11 -Wall -Wextra -pedantic test_heap.cc


/a.exe


Push time: 177ms Pop time: 2504ms Sum: -2014260032

I have used gprof to profile but the compiler inlines everything into the main function so gprof unfortunately doesn't give anything useful in this case. And I don't feel like the results are useful if disabling optimizations to measure performance...

Note that I'm printing the sum only to avoid the compiler from removing the benchmark code because it isn't used.

Here is the implementation heap.hpp:

```
#include
#include // std::less
#include // std::swap
#include

namespace elads{

// A binary min-heap implemented using the given comparator.
template >
class heap{
public:
void push(const T& value){
auto idx = m_data.size();
m_data.emplace_back(value);
sift_up(idx);
}

void pop(){
if(m_data.empty()){
throw std::runtime_error("Stack is empty!");
}

if(m_data.size() == 1){
m_data.clear();
return;
}

swap(0, m_data.size() - 1);
m_data.erase(m_data.end()-1);
sift_down(0);
}

const T& top() const {
if(m_data.empty()){
throw std::runtime_error("Stack is empty!");
}
return m_data.front();
}

bool empty() const{
return m_data.empty();
}

private:
std::vector m_data;
Comparator m_cmp;

bool less(size_t lhs, size_t rhs) const{
return m_cmp(m_data[lhs], m_data[rhs]);

Drop the checks

Right now, your pop() and top() both check for emptiness and throw. assert() would be better - you don't want these functions throwing. It's likely that your user will check for empty() first anyway - and if they don't, make sure they understand that they have to. With that, our top() becomes trivial:

const T& top() const {
    return m_data.front();
}

And our pop() is a few lines shorter.

Swapping

Two unrelated comments to make about swapping. First, in your pop(), you swap the first and last elements and then erase the last one. But you don't actually need to do that. We don't care that the last element is the first one when we erase it. Just move the last one into the first one:

m_data.front() = std::move(m_data.back());
m_data.pop_back();

That'll save some unnecessary operations.

The second comment is about your member function swap(). It's a little confusing in that it doesn't swap the arguments passed in - it swaps those indices. So prefer to name it swap_idx() or something along those lines just for clarity.

Special cases

In your pop(), you start with the special case that size() == 1. But there's nothing special about that case for the purpose of your algorithm. sift_down() will just do nothing. So you don't need it. That reduces your pop() down to:

void pop() {
    m_data.front() = std::move(m_data.back());
    m_data.pop_back();
    sift_down(0);
}

Overflow

You have this enormous comment block and logic in sift_down() describing overflow cases for indices. You are really not going to have a heap large enough to have potential for overflow. I wouldn't worry about it. It just makes your logic more complicated than it needs to be. Drop it.

Push it. Push it real good

If you have push(const T&), you may as well add push(T&& ), and then while we're at it, also add emplace(Args&&...). You could have them all forward to a common implementation:

void push(const T& value) { emplace(value); }
void push(T&& value) { emplace(std::move(value); }

template 
void emplace(Args&&... args) {
    auto idx = m_data.size();
    m_data.emplace_back(std::forward(args)...);
    sift_up(idx);
}

Arbitrary Comparators

If you allow for a templated Comparator - you need to allow the user to pass one in via a constructor. As-is, it really only works with default-constructible types. Furthermore, I'd suggest inheriting from the comparator to take advantage of the empty base optimization - std::less<> for instance is empty, so can save that space.

StackExchange Code Review Q#114457, answer score: 7