Template Class BinaryHeap

Nested Relationships

Nested Types

Class Documentation

template<typename _T, class LessThan = std::less<_T>>
class BinaryHeap

This class provides an implementation of an updatable min-heap. Using it is a bit cumbersome, as it requires keeping track of the BinaryHeap::Element* type, however, it should be as fast as it gets with an updatable heap.

Public Types

using EventAfterInsert = void (*)(Element*, void*)

Event that gets called after an insertion.

using EventBeforeRemove = void (*)(Element*, void*)

Event that gets called just before a removal.

Public Functions

inline BinaryHeap()
inline BinaryHeap(LessThan lt)
inline ~BinaryHeap()
inline void onAfterInsert(EventAfterInsert event, void *arg)

Set the event that gets called after insertion.

inline void onBeforeRemove(EventBeforeRemove event, void *arg)

Set the event that gets called before a removal.

inline void clear()

Clear the heap.

inline Element *top() const

Return the top element. nullptr for an empty heap.

inline void pop()

Remove the top element.

inline void remove(Element *element)

Remove a specific element.

inline Element *insert(const _T &data)

Add a new element.

inline void insert(const std::vector<_T> &list)

Add a set of elements to the heap.

inline void buildFrom(const std::vector<_T> &list)

Clear the heap, add the set of elements list to it and rebuild it.

inline void rebuild()

Rebuild the heap.

inline void update(Element *element)

Update an element in the heap.

inline bool empty() const

Check if the heap is empty.

inline unsigned int size() const

Get the number of elements in the heap.

inline void getContent(std::vector<_T> &content) const

Get the data stored in this heap.

inline void sort(std::vector<_T> &list)

Sort an array of elements. This does not affect the content of the heap.

inline LessThan &getComparisonOperator()

Return a reference to the comparison operator.

class Element

When an element is added to the heap, an instance of Element* is created. This instance contains the data that was added and internal information about the position of the data in the heap’s internal storage.

Public Members

_T data

The data of this element.