Generic min heap in C++

Question

I have recently started programming in C++. I have coded in MATLAB and C in the past. The following code implements a min heap as a generic class in C++. I would like to get some feedback on the coding style and if you guys have any tips on how to make the code more acceptable to the C++ community. The code works as intended.

#include <iostream>
#include <vector>
using namespace std;

template<class T>
class PriorityQueue {
public:
    PriorityQueue() {
    }
    ;
    PriorityQueue(const vector<T>& data);
    PriorityQueue(const T data[], int length);

    T pop();
    void push(T element);
    void changePriority(T element);
    void deleteElement(T element);
    int getTotalElements();
    int getElementIndex(T element);
    T getElement(int index);
    void printQueue();

private:
    vector<T> m_queue;
    vector<unsigned int> getChildrenIndex(int index);
    int getParentIndex(int index);
    bool isRoot(int index);
    void heapify();
    void bubbleup(int index);
    void sinkDown(int index = 0);
    void swapElements(int index1, int index2);

}
;

template<typename T>
PriorityQueue<T>::PriorityQueue(const vector<T>& data) {
    for (unsigned int i = 0; i < data.size(); i++) {
        m_queue.push_back(data[i]);
    }

    heapify();

}

template<typename T>
PriorityQueue<T>::PriorityQueue(const T data[], int length) {
    for (unsigned int i = 0; i < length; i++) {
        m_queue.push_back(data[i]);
    }

    heapify();

}

template<typename T>
void PriorityQueue<T>::heapify() {
    for (int i = m_queue.size() - 1; i >= 0; --i) {
        sinkDown(i);
    }
}

template<typename T>
void PriorityQueue<T>::push(T element) {
    m_queue.push_back(element);

    if (m_queue.empty()) {
        return; //only node
    }
    //else bubble up the last node
    bubbleup(getTotalElements() - 1);
}

template<typename T>
T PriorityQueue<T>::pop() {
    T element;
    if (m_queue.empty()) {
        cout << "Nothing to pop. Queue is empty" << endl;
        element = 0;
    }
    // Get the root element
    element = m_queue[0];

    // Add the last element to the root and resize
    m_queue[0] = m_queue[m_queue.size() - 1];
    m_queue.resize(m_queue.size() - 1);

    // Sink down the root element to get the min heap again.
    sinkDown();

    // return the root element
    return element;

}
template<typename T>
void PriorityQueue<T>::changePriority(T element) {

    int index = getElementIndex(element);

    if (index == -1) {
        return; // This vertex is not there in the priority queue.
    }

    m_queue[index].setCost(element.getCost());
    m_queue[index].setPrevNode(element.getPrevNode());

    // else update the cost of this vertex and either bubbleup or sinkDown.
    int parentIndex = getParentIndex(index);

    if (isRoot(index)) {
        sinkDown(index);
        return;
    }

    if (m_queue[parentIndex] > m_queue[index]) {
        bubbleup(index);
    } else {
        sinkDown(index);
    }

}

template<typename T>
void PriorityQueue<T>::deleteElement(T element) {
    int index = getElementIndex(element);
    if (index == -1) {
        return; //this vertex does not exist in the queue.
    }

    // Fill up the node with the last node in the queue and either bubble up or sink down.

    m_queue[index] = m_queue[m_queue.size() - 1];
    m_queue.resize(m_queue.size() - 1);

    int parentIndex = getParentIndex(index);

    if (isRoot(index)) {
        sinkDown(index);
        return;
    }

    if (m_queue[parentIndex] > m_queue[index]) {
        bubbleup(index);
    } else {
        sinkDown(index);
    }

}

template<typename T>
int PriorityQueue<T>::getParentIndex(int index) {
    int parentIndex;
    if (isRoot(index)) {
        parentIndex = index; // returns the same index if it's the root element
    }
    //else
    parentIndex = static_cast<int>((index - 1) / 2);
    return parentIndex;
}

template<typename T>
bool PriorityQueue<T>::isRoot(int index) {
    if (index == 0) {
        return true;
    }
    // else
    return false;
}

template<typename T>
vector<unsigned int> PriorityQueue<T>::getChildrenIndex(int index) {
    vector<unsigned int> childrenIndex;

    if ((2 * index + 1) < m_queue.size()) {
        childrenIndex.push_back(2 * index + 1);
    }

    if ((2 * index + 2) < m_queue.size()) {
        childrenIndex.push_back(2 * index + 2);
    }

    return childrenIndex;

}

template<typename T>
int PriorityQueue<T>::getTotalElements() {
    return m_queue.size();
}

template<typename T>
int PriorityQueue<T>::getElementIndex(T element) {
    // returns -1 if element not found
    int index = -1;
    for (int i = 0; i < m_queue.size(); i++) {
        if (m_queue[i] == element) {
            index = i;
            break;
        }
    }

    // else
    return index;
}

template<typename T>
void PriorityQueue<T>::bubbleup(int index) {
    bool isMinHeap = false;
    int currentIndex = index;

    while (!isMinHeap) {
        if (isRoot(currentIndex)) {
            isMinHeap = true;
            return; // It's the root node.
        }

        // else
        int parentIndex = getParentIndex(currentIndex);

        if (m_queue[parentIndex] > m_queue[currentIndex]) {
            swapElements(currentIndex, parentIndex);
            currentIndex = parentIndex;
        } else {
            isMinHeap = true;
        }

    }
}

template<typename T>
void PriorityQueue<T>::sinkDown(int index) {
    int currentIndex = index;
    bool isMinHeap = false;
    while (!isMinHeap) {
        vector<unsigned int> childrenIndex = getChildrenIndex(currentIndex);
        int NumChildren = childrenIndex.size();
        switch (NumChildren) {
        case 0:
            isMinHeap = true; // It's a leaf. No need to sink down any further.
            break;

        case 1: // 1 children

            if (m_queue[currentIndex] > m_queue[childrenIndex[0]]) {
                swapElements(currentIndex, childrenIndex[0]);
                currentIndex = childrenIndex[0];
            } else {
                isMinHeap = true;
            }
            break;

        case 2:
            // Get the smaller children first.
            int smallerChildrenIndex =
                    (m_queue[childrenIndex[0]] < m_queue[childrenIndex[1]]) ?
                            childrenIndex[0] : childrenIndex[1];
            if (m_queue[currentIndex] > m_queue[smallerChildrenIndex]) {
                swapElements(currentIndex, smallerChildrenIndex);
                currentIndex = smallerChildrenIndex;
            } else {
                isMinHeap = true;
            }
            break;
        }
    }
}

template<typename T>
void PriorityQueue<T>::swapElements(int index1, int index2) {

    T temp = m_queue[index1];
    m_queue[index1] = m_queue[index2];
    m_queue[index2] = temp;
}

template<typename T>
T PriorityQueue<T>::getElement(int index) {
    return m_queue[index];
}

template<typename T>
void PriorityQueue<T>::printQueue() {
    for (typename vector<T>::iterator it = m_queue.begin(); it != m_queue.end();
            it++) {
        cout << *it << endl;
    }
}

Answer 1

I wont' comment on the algorithmic details of your implementation, just the general coding style.

Constness

When a member function doesn't change the inner state of your object, declare it as const. This makes their intention clearer and allows them to be used in cases where you only have a const reference to your container.

The same basically applies for function parameters. If you don't change them, take them as const& rather than by value. This way you will prevent unnecessary copies.

Simplifications

When you're implementing a default constructor that does nothing special, say so be writing PriorityQueue() = default; instead of writing an empty contructor body.

Your loop in printQueue can be improved in multiple ways. First you can use auto it instead of writing the whole tpye. Let the compiler figure out the actual type. To make the loop even more readable, you can also use the syntax for range-based-for loops, as follows.

for (auto const& it: m_queue)
    cout << it << endl;

Just note that it now is not an iterator anymore, but an acutal element. Also you should use const& (or &) again, to prevent unnecessary copies.

The if statement in your isRoot method is not necessary. Simply use return index == 0;

In your constructor taking a vector its you could directly use m_queue = data; instead of iterating over the vector manually. What would be even better is to directly initialize your member in the initializer list of the constructor:

template<typename T>
PriorityQueue<T>::PriorityQueue(const std::vector<T>& data)
    : m_queue(data)
{
    heapify();
}

In the push mehtod the check for empty is unecessary, since that can never be the case, since you justed pushed an element.

Prefer emplace... over push...

If you want to put elements into a container use the emplace methods rather than the push methods. This will create an element in place, instead of creating temporary objects. There are cases where push might be useful, but those are rare.

Prefer STL algorithms

There are many generalized algorithms in the Standard Template Library. You should make use of them, especially when dealing with container like classes. For example your getElementIndex method could be written like:

auto pos = std::find(m_queue.begin(), m_queue.end(), element);
return pos == m_queue.end() ? -1 : std::distance(m_queue.begin(), pos);

In the case of a vector this also has the same complexity as your own implementation. The same applies for your swapElements method. Simply use std::swap there.

Container classes

When writing container like classes you should adhere to the interfaces that are already provided by other containers from the STL. This makes it easier to understand what to expect from the class and how to properly use it. It also allows the class to be used in generalized algorithms that rely on such an interface. E.g. your getTotalElements method should be renamed size. A good overview can be found here. Of course you don't have to implement all of those methods, just those that are most useful and expected from a priority queue class. Most of those methods would be delegations anyway, since you already use a container class internally. For example a good start would be iterator support, so one could e.g. write

for (auto const& e : q)
    ;// do stuff with the element e

without worrying about indices. This would look like this (the formatting is just used here to save space).

using iterator = typename std::vector<T>::iterator;
using const_iterator = typename std::vector<T>::const_iterator;

iterator begin() { return m_queue.begin(); }
const_iterator begin() const { return m_queue.begin(); }
const_iterator cbegin() const { return begin(); }

iterator end() { return m_queue.end(); }
const_iterator end() const { return m_queue.end(); }
const_iterator cend() const { return end(); }

Template argument type

Looking at your changePriority method it seems as your class only accepts template arguments of a specific type, as the method directyl accesses getCost, setCost, getPrevNode and setPrevNode. You should prevent the (accidental) misues of your class by adding a static_assert. I don't know what condition you want, I assume you want to only allow certain base classes. In this case you could write:

template <typename T>
class PriorityQueue
{
    static_assert(std::is_base_of<BaseClass, T>::value, "Wrong template parameter. Has to be a base of BaseClass!");
    //... other stuff.
};

This way the user will get a sane error mesagge, when the template argument is wrong. If you don't require a specific base class, but the presence of specific members, you could use things like typetraits. As a rough sketch, something like this could work:

template <typename T>
auto valid_type_impl(int)
-> decltype(
    std::declval<T&>().setCost(std::declval<T&>().getCost()),
    std::declval<T&>().setPrevNode(std::declval<T&>().getPrevNode()),
    // missing comparison and stream operator
    std::true_type{});

template <typename T>
std::false_type valid_type_impl(...);

template <typename T>
using is_valid_type = decltype(valid_type_impl<T>(0));

template <typename T>
class PriorityQueue
{
    static_assert(is_valid_type<T>::value, "Wrong template parameter");
    //...
}

Some additional remarks without comments, just a link to the C++ CoreGuidelines

Use #include guards for all .h files.

Don't write using namespace in a header file

Avoid endl