6
\$\begingroup\$

I implemented a D-ary max heap backed by a vector for resizing. I would like to know any possible improvements in performance, design, and in the code in general.

#pragma once
#include <vector>
#include <iostream>
#include "Comparators.h"

template<typename T>
class DHeap
{

public:
    DHeap();
    DHeap(unsigned);
    ~DHeap();

    T extractMax();
    void insert(const T&);
    T increaseKey(unsigned, const  T&);
    bool empty() const{ return vec.size() == 0; }

private:
    std::vector<T> vec;
    int D;

    void maxheapify(unsigned);
    void swim(int);
    unsigned max(unsigned, unsigned) const;
    unsigned firstChild(unsigned) const;
    int parent(int) const;
    void ensureCapacity();
    int cmp(const T &, const T&) const;
    int cmpI(unsigned, unsigned) const;

    friend std::ostream & operator<<(std::ostream &os, const DHeap<T>& p)
    {
        for (const T& d : p.vec)
            os << d << " ";
        return os;
    }
};




template <typename T>
DHeap<T>::DHeap() : DHeap(4){}

template <typename T>
DHeap<T>::DHeap(unsigned d) :D(d){}


template <typename T>
DHeap<T>::~DHeap(){}

template <typename T>
T DHeap<T>::extractMax()
{
    if (vec.size() < 1)
        throw new std::underflow_error("underflow");

    T max = vec[0];
    vec[0] = vec.back();
    vec.pop_back();
    maxheapify(0);

    return max;
}

template <typename T>
void DHeap<T>::insert(const T &element)
{
    ensureCapacity();
    vec.push_back(element);
    swim(vec.size()-1);
}

template <typename T>
T DHeap<T>::increaseKey(unsigned index, const T &element)
{
    if (cmp(element, vec[index]) < 0)
        throw new std::invalid_argument("new key must be greater than previous");

    T old = vec[index];
    vec[index] = element;
    swim(index);

    return old;
}

template <typename T>
void DHeap<T>::maxheapify(unsigned index)
{
    unsigned first = 0;
    while ((first = firstChild(index)) < vec.size())
    {
        unsigned largest = first++;
        while (first <= D*(index + 1) && first < vec.size())
            largest = max(largest, first++);

        if (cmpI(largest,index) <= 0) break;

        std::swap(vec[largest], vec[index]);
        index = largest;
    }
}

template<typename T>
unsigned DHeap<T>::max(unsigned a, unsigned b) const
{
    return cmpI(a, b) < 0 ? b : a;
}
template<typename T>
int  DHeap<T>::cmp(const T & a, const T& b) const
{
    return Comparators::compare(a, b);
}
template<typename T>
int DHeap<T>::cmpI(unsigned i, unsigned j) const
{
    return cmp(vec[i], vec[j]);
}

template <typename T>
void DHeap<T>::swim(int index)
{
    int p = 0;
    while (index > 0 && cmpI(p = parent(index), index) < 0)
    {
        std::swap(vec[p], vec[index]);
        index = p;
    }

}

template <typename T>
unsigned DHeap<T>::firstChild(unsigned index) const
{
    return D* index + 1;
}
template <typename T>
int DHeap<T>::parent(int index) const
{
    return (index - 1) / D;

}
template <typename T>
void DHeap<T>::ensureCapacity()
{
    if (vec.size() == vec.capacity())
        vec.reserve(3 * vec.size() / 2 + 1);
}

This are some template method that I use for comparing inside the heap

#pragma once
#include <memory>

namespace Comparators
{

    template<typename T>  int compare(const T &, const T &);
    template<typename T>  int compare(const T*, const T*);
    template<typename T>  int compare(T*, T*);
    template<typename T>  int compare(std::shared_ptr<T> a, std::shared_ptr<T> b);


    template<typename T>
    int compare(const T &a, const T &b)
    {
        std::less<T> func;

        if (func(a, b)) return -1;
        if (func(b, a)) return 1;
        return 0;
    }

    template<typename T>
    int compare(const T* a, const T* b)
    {
        return compare(*a, *b);
    }

    template<typename T>
    int compare(T* a, T* b)
    {
        return compare(*a, *b);
    }

    template<typename T>
    int compare(std::shared_ptr<T> a, std::shared_ptr<T> b)
    {
        return compare(*a, *b);
    }

}
\$\endgroup\$
5
\$\begingroup\$

Let's start with the signature:

template<typename T>
class DHeap;

This is unsufficient. You provide some default comparators, which would be fine if my type happened to have operator< implemented. But what if it didn't? You need to let the user provide his own comparator. Also you are using 3-way compare when simple binary is sufficient. The typical way to do this would be:

template <typename T, typename Compare = std::less<T>>
class DHeap;

And have a member variable Compare compare, and add constructors to let the user pass in a const Compare&. You should then drop your Comparators.h

Interface

bool empty() const should return vec.empty(), not vec.size() == 0.

For performance, typically instead of providing T extractMax(), you should provide:

T const& maxElement() const; // or top()
void pop();

There are two reasons for this. The goal of a heap is to make it as efficient as possible to grab the top element. As you wrote it, extractMax() is logarithmic (because maxheapify() is). So that sort of defeats the purpose. Secondly, because you're extracting at the same time, you're requiring an additional copy (you can't return a reference because it would dangle). So that's less efficient too. This way, you can have a constant time zero-copy implementation:

T const& top() const { return vec[0]; }

Though one comment on extractMax, you would have definitely wanted to move into max, not copy:

T max = std::move(vec[0]);
vec[0] = std::move(vec.back());

For those types that have cheap move, this will save you some time.

You also don't need a destructor. The default one works great.

Should increaseKey() really be a public (or any) member? The user shouldn't be aware of the actual indices in your data structure. That seems like it breaks encapsulation to me.

Insertion

For C++03, void insert(const T&) is correct and sufficient. For C++11, we can do a lot better. First, I want to be able to move a T into your heap, so you should support that:

void insert(T&& element) {
    ensureCapacity();
    vec.push_back(std::move(element));
    swim(vec.size() - 1);
}

And also I should be able to construct an element in place. Because why should I incur an extra copy/move if I don't have to?

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

That should do it.

Implementation Details

maxheapify is confusingly implemented. I have trouble following the loop since you're trying to do too many things on one line. First, the inner loop:

unsigned largest = first++;
while (first <= D*(index + 1) && first < vec.size())
    largest = max(largest, first++);

That is the same as:

unsigned largest = first++;
while (first <= D*(index + 1) && first < vec.size()) {
    largest = max(largest, first);
    ++first;
}

Which is the same as:

for (unsigned largest = first, ++first;
     first <= D * (index + 1) && first < vec.size();
     ++first) 
{
    largest = max(largest, first);
}

Oh I get it now, we're finding the max of all the children. Also max is a very confusing function here. max to most people means std::max(), so my initial thought as that obviously first > largest at every iteration. And then I found your implementation. Let's not do it this way, and use the compare directly:

largest = compare(vec[largest], vec[first]) ? first : largest;

That is easy to understand. And let's actually factor out that loop that I wrote up there. So full rewrite of that function:

template <typename T>
void DHeap<T>::maxheapify(unsigned index)
{
    while ((unsigned first = firstChild(index)) < vec.size())
    {
        unsigned largest = findLargest(first, 
                             std::min(firstChild(index + 1) + 1, vec.size()));
        if (compare(vec[largest], vec[index])) {
            break;
        }

        using std::swap;
        swap(vec[largest], vec[index]);
        index = largest;
    }
}

template <typename T>
unsigned DHeap<T>::findLargest(unsigned from, unsigned to)
{
    unsigned largest = from++;
    for (; from < to; ++from ) {
        largest = compare(vec[largest], vec[from]) ? from : largest;
    }
    return largest;
}

I find that much easier to parse. Note also the using std::swap. That let's ADL find swap() if necessary.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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