Min-Heap structure with property v[i]<v[2*i+1] and v[i]<v[2*i+2] Parent at index i has children at indices 2*i+1 and 2*i+2 Smallest values are stored closer to root of tree. More...
#include <WEMHeap.h>
Public Member Functions | |
| WEMHeap () | |
| Standard constructor. More... | |
| WEMHeap (WEMHeap &&) noexcept=default | |
| WEMHeap & | operator= (WEMHeap &&) noexcept=default |
| ~WEMHeap () override | |
| Standard destructor. More... | |
| T * | root () |
| Returns the root (first) element of this heap, typecast from WEMPrimitive to T. More... | |
| const T * | root () const |
| Returns the root (first) element of this heap, typecast from WEMPrimitive to T. More... | |
| void | swap (unsigned int i, unsigned int j) override |
| Swaps two heap elements given by their indices and resorts this heap. More... | |
| void | insert (WEMPrimitive *wp) |
| Inserts the given heap element and resorts this heap. More... | |
| void | insert (WEMPrimitive *wp, double v) |
| Inserts the given heap element and sets its value, and resorts this heap. More... | |
| void | update (WEMPrimitive *wp, double nv) |
| Updates given heap element with the given value and resorts this heap. More... | |
| int | remove (WEMPrimitive *wp) override |
| Removes the given heap element and resorts this heap. More... | |
| void | sort () |
| Sorts this heap. More... | |
| void | clear () override |
| Remove all elements from heap. More... | |
 Public Member Functions inherited from ml::WEMVector< WEMPrimitive > | |
| WEMVector (unsigned int init=0) | |
| Standard constructor. More... | |
| WEMVector (WEMVector &&other) noexcept | |
| WEMVector & | operator= (WEMVector &&other) noexcept |
| virtual | ~WEMVector () |
| Standard destructor. More... | |
| unsigned int | num () const |
| Returns the number of elements in this vector. More... | |
| WEMPrimitive * | at (unsigned int pos) const |
| Returns the element at the given position or returns NULL if out of range. More... | |
| WEMPrimitive * | first () |
| Returns the first element. More... | |
| const WEMPrimitive * | first () const |
| Returns the first element. More... | |
| WEMPrimitive * | last () |
| Returns the last element. More... | |
| const WEMPrimitive * | last () const |
| Returns the last element. More... | |
| virtual unsigned int | append (WEMPrimitive *elem) |
| Appends the given element to back of this vector. More... | |
| virtual void | deleteAt (unsigned int pos) |
| Deletes the element at the given position. More... | |
| virtual void | deleteLast () |
| Deletes the last element of this vector. More... | |
| virtual int | remove (WEMPrimitive *elem) |
| Deletes the element given by its pointer. More... | |
| virtual int | lookup (WEMPrimitive *elem) const |
| Searches for the given element in this vector and returns its position. More... | |
| virtual int | removeUnSwapped (WEMPrimitive *elem) |
| Deletes the element given by its pointer. Keeps the order of the elements! More... | |
| virtual void | destroy () |
| Deletes all elements in this vector. More... | |
| virtual void | replace (WEMPrimitive *elem, unsigned int pos) |
| Replaces the given position with the given element. More... | |
| void | reserve (unsigned int init) |
Reserves init elements, copies old ones if existing. More... | |
Additional Inherited Members | |
| Protected Member Functions inherited from ml::WEMVector< WEMPrimitive > | |
| virtual void | expand () |
| Grow vector, add extra block of size BLOCKSIZE. More... | |
| virtual unsigned int | appendUnsafe (WEMPrimitive *elem) |
| Append element to back of vector, don't check on element being non-NULL. More... | |
Detailed Description
template<class T>
class ml::WEMHeap< T >
Min-Heap structure with property v[i]<v[2*i+1] and v[i]<v[2*i+2] Parent at index i has children at indices 2*i+1 and 2*i+2 Smallest values are stored closer to root of tree.
Elements are sorted while inserting them in the heap.
Constructor & Destructor Documentation
◆ WEMHeap() [1/2]
| ml::WEMHeap< T >::WEMHeap |
◆ WEMHeap() [2/2]
|
defaultnoexcept |
◆ ~WEMHeap()
|
override |
Member Function Documentation
◆ clear()
|
overridevirtual |
Remove all elements from heap.
Reimplemented from ml::WEMVector< WEMPrimitive >.
Definition at line 278 of file WEMHeap.h.
References boost::at(), and ml::WEMVector< T, fixedBufferSize >::clear().
◆ insert() [1/2]
| void ml::WEMHeap< T >::insert | ( | WEMPrimitive * | wp | ) |
Inserts the given heap element and resorts this heap.
Definition at line 124 of file WEMHeap.h.
References ml::WEMVector< T, fixedBufferSize >::appendUnsafe(), and ml::WEMPrimitive::getHeapPosition().
◆ insert() [2/2]
| void ml::WEMHeap< T >::insert | ( | WEMPrimitive * | wp, |
| double | v | ||
| ) |
Inserts the given heap element and sets its value, and resorts this heap.
Definition at line 138 of file WEMHeap.h.
References ml::WEMVector< T, fixedBufferSize >::appendUnsafe(), ml::WEMPrimitive::getHeapPosition(), and ml::WEMPrimitive::setHeapValue().
◆ operator=()
|
defaultnoexcept |
◆ remove()
|
override |
Removes the given heap element and resorts this heap.
Definition at line 159 of file WEMHeap.h.
References boost::at(), ml::WEMPrimitive::getHeapPosition(), ml::WEMMinHeapCompare::less(), and ml::WEMPrimitive::setHeapPosition().
◆ root() [1/2]
| T * ml::WEMHeap< T >::root |
Returns the root (first) element of this heap, typecast from WEMPrimitive to T.
Definition at line 90 of file WEMHeap.h.
References ml::WEMVector< T, fixedBufferSize >::first(), and T.
◆ root() [2/2]
| const T * ml::WEMHeap< T >::root |
Returns the root (first) element of this heap, typecast from WEMPrimitive to T.
◆ sort()
| void ml::WEMHeap< T >::sort |
Sorts this heap.
Definition at line 260 of file WEMHeap.h.
References ml::WEMVector< T, fixedBufferSize >::append(), boost::at(), ml::WEMVector< T, fixedBufferSize >::at(), and ml::WEMVector< T, fixedBufferSize >::num().
◆ swap()
|
overridevirtual |
Swaps two heap elements given by their indices and resorts this heap.
Reimplemented from ml::WEMVector< WEMPrimitive >.
Definition at line 114 of file WEMHeap.h.
References boost::at(), and ml::WEMVector< T, fixedBufferSize >::swap().
◆ update()
| void ml::WEMHeap< T >::update | ( | WEMPrimitive * | wp, |
| double | nv | ||
| ) |
Updates given heap element with the given value and resorts this heap.
Definition at line 194 of file WEMHeap.h.
References ml::WEMPrimitive::getHeapPosition(), ml::WEMPrimitive::getHeapValue(), and ml::WEMPrimitive::setHeapValue().
The documentation for this class was generated from the following file:
- MeVisLab/Standard/Sources/ML/MLWEM/WEMDataStructure/WEMHeap.h
