how to implement minheap using template

Question

I need to create a minheap template which includes nodes in it.

The problem I have is that I don't know if I need to create a node template class as well, or should it be included inside the heap template class as a struct?

Answer 1

Min heaps aren’t usually (never?) implemented using explicit nodes – since a heap is always left-filled (“complete”) and thus has a well-defined structure, that would be unnecessarily inefficient since the handling of nodes and node links introduces quite a bit of overhead, not to mention destroying locality of reference, leading to cache misses and poor performance.

(The same goes for max heaps of course.)

Instead, they are implemented using arrays. In fact, the C++ standard library already includes the functions make_heap, push_heap and pop_heap to work on iterator Ranges. Use them in conjunction with a vector and you got your heap.

Answer 2

Basically the nodes aren't needed to be implemented with the nodes as template class. The implementation might be something like this declaration:

template <class T>
class MinHeap {
private:
    std::vector<T> _heap;
    int _maxSize;
    int _size;

public:
    MinHeap(int maxSize);
    ~MinHeap();
    void Insert(T elem);
     T RemoveMin();

private:
    int LeftChild(int pos);
    int RightChild(int pos);
    int Parent(int pos);
    boolean IsLeaf(int pos);
    void Swap(int pos1, int pos2);
    void PushDown(int position);
};