Как реализовать Minheap с помощью шаблона

Question

Мне нужно создать шаблон minheap, который включает в себя узлы в нем.

У меня проблема в том, что я не знаю, нужно ли мне также создавать класс шаблона узла или он должен быть включен в класс шаблона кучи в виде структуры?

Answer 1

Минимальные кучи обычно (никогда?) Не реализуются с использованием явных узлов - поскольку куча всегда заполнена слева («завершена») и, таким образом, имеет четко определенную структуру, что было бы излишне неэффективным, поскольку обработка узлови ссылки на узлы вносят немало накладных расходов, не говоря уже о разрушении локальности ссылок, что приводит к пропаданию кэша и низкой производительности.

(То же самое относится и к максимальным кучам, конечно.)

Вместо этогоони реализованы с использованием массивов.На самом деле стандартная библиотека C ++ уже включает функции make_heap, push_heap и pop_heap для работы с диапазонами итераторов.Используйте их вместе с vector, и вы получите свою кучу.

Answer 2

По сути, узлы не должны быть реализованы с узлами в качестве класса шаблона. Реализация может быть что-то вроде этого объявления:

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);
};