gum::Heap< Val, Cmp > Class Template Reference

Heap data structure. More...

#include <agrum/base/core/heap.h>

Public Types
using	value_type = Val
	Types for STL compliance.
using	reference = Val&
	Types for STL compliance.
using	const_reference = const Val&
	Types for STL compliance.
using	pointer = Val*
	Types for STL compliance.
using	const_pointer = const Val*
	Types for STL compliance.
using	size_type = std::size_t
	Types for STL compliance.
using	difference_type = std::ptrdiff_t
	Types for STL compliance.

Public Member Functions
Constructors / Destructors
	Heap (Cmp compare=Cmp(), Size capacity=GUM_HEAP_DEFAULT_CAPACITY)
	Basic constructor: creates an empty heap.
	Heap (std::initializer_list< Val > list)
	Initializer list constructor.
	Heap (const Heap< Val, Cmp > &from)
	Copy constructor.
	Heap (Heap< Val, Cmp > &&from) noexcept
	Move constructor.
	~Heap ()
	Class destructor.
Operators
Heap< Val, Cmp > &	operator= (const Heap< Val, Cmp > &from)
	Copy operator.
Heap< Val, Cmp > &	operator= (Heap< Val, Cmp > &&from) noexcept
	Move operator.
const Val &	operator[] (Size index_elt) const
	Returns the element at index index_elt from the heap.
Accessors / Modifiers
const Val &	top () const
	Returns the element at the top of the heap.
Val	pop ()
	Removes the top element from the heap and return it.
void	eraseTop ()
	Removes the top of the heap (but does not return it).
void	eraseByPos (Size index)
	Removes the element positioned at "index" from the heap.
void	erase (const Val &val)
	Removes a given element from the heap (but does not return it).
Size	insert (const Val &val)
	inserts a new element (actually a copy) in the heap and returns its index
Size	insert (Val &&val)
	Inserts a new element (by moving it) in the heap and returns its index.
template<typename... Args>
Size	emplace (Args &&... args)
	Emplace a new element in the heap and returns its index.
Size	size () const noexcept
	Returns the number of elements in the heap.
bool	empty () const noexcept
	Indicates whether the heap is empty.
bool	contains (const Val &) const
	Indicates whether the heap contains a given value.
std::string	toString () const
Fine tuning
Size	capacity () const noexcept
	Returns the size of the internal structure storing the heap.
void	resize (Size new_size)
	Changes the size of the the internal structure storing the heap.

Private Member Functions
Size	_restoreHeap_ ()
	After inserting an element at the end of the heap, restore heap property.

Private Attributes
std::vector< Val >	_heap_
	An array storing all the elements of the heap.
Size	_nb_elements_ {0}
	The number of elements in the heap.
Cmp	_cmp_
	Comparison function.

Detailed Description

template<typename Val, typename Cmp = std::less< Val >>
class gum::Heap< Val, Cmp >

Heap data structure.

This structure is a basic heap data structure, i.e., it is a container in which elements are sorted according to a weak ordering. Given this ordering, we do have access in O(1) to the "smallest" element contained by the structure. Insertions and deletions of elements are processed in O(ln n), where n is the number of elements in the heap. In addition to the classical pop, top and push functions, Heap provide direct accessors to the elements in the heap (see operator[]). However, these can only be accessed in read-only mode.

Usage example:

// create a heap of integers, the top element is the smallest element
Heap<int> heap1;
 
// create a heap of floats, the top element is the greatest
Heap<float> heap2 (std::greater<float>());
 
// insert elements into the heap
heap1.insert (8);
heap1.insert (10);
heap1.insert (2);
heap1.insert (23);
heap1.insert (24);
heap1.insert (10);
heap1.insert (10);
 
// copy a heap into another
Heap<int> heap2 = heap1;
 
// get the number of elements of the heap
std::cerr << heap2.size() << std::endl;
 
// get the top element but do not remove it
std::cerr << heap2.top() << std::endl;
 
// get and remove the top element of the heap
std::cerr << heap2.pop() << std::endl;
 
// remove the top element but do not return it (faster than above)
heap2.eraseTop();
 
// erase in heap1 value 8
heap1.eraseByVal (8);
 
// erase element at position 3 (see function erase for the
// meaning of position 3)
heap1.erase (3);
 
// get the element at position 3
heap1[3];
 
// check whether element 24 belongs to the heap
heap1.contains (24);

Template Parameters

Val	The gum::Heap values type.
Cmp	The comperator used to sort elements in the gum::Heap.

Definition at line 141 of file heap.h.

Member Typedef Documentation

const_pointer

template<typename Val, typename Cmp = std::less< Val >>

using gum::Heap< Val, Cmp >::const_pointer = const Val*

Types for STL compliance.

Definition at line 149 of file heap.h.

const_reference

template<typename Val, typename Cmp = std::less< Val >>

using gum::Heap< Val, Cmp >::const_reference = const Val&

Types for STL compliance.

Definition at line 147 of file heap.h.

difference_type

template<typename Val, typename Cmp = std::less< Val >>

using gum::Heap< Val, Cmp >::difference_type = std::ptrdiff_t

Types for STL compliance.

Definition at line 151 of file heap.h.

pointer

template<typename Val, typename Cmp = std::less< Val >>

using gum::Heap< Val, Cmp >::pointer = Val*

Types for STL compliance.

Definition at line 148 of file heap.h.

reference

template<typename Val, typename Cmp = std::less< Val >>

using gum::Heap< Val, Cmp >::reference = Val&

Types for STL compliance.

Definition at line 146 of file heap.h.

size_type

template<typename Val, typename Cmp = std::less< Val >>

using gum::Heap< Val, Cmp >::size_type = std::size_t

Types for STL compliance.

Definition at line 150 of file heap.h.

value_type

template<typename Val, typename Cmp = std::less< Val >>

using gum::Heap< Val, Cmp >::value_type = Val

Types for STL compliance.

Definition at line 145 of file heap.h.

Constructor & Destructor Documentation

Heap() [1/4]

template<typename Val, typename Cmp>

gum::Heap< Val, Cmp >::Heap ( Cmp compare = Cmp(), Size capacity = GUM_HEAP_DEFAULT_CAPACITY )

explicit

Basic constructor: creates an empty heap.

Parameters

compare	a function taking two elements in argument, say e1 and e2, and returning a Boolean indicating wether e1 < e2, i.e., whether e1 should be nearer than e2 to the top of the heap.
capacity	the size of the internal data structures containing the elements (could be for instance vectors or hashtables).

Definition at line 59 of file heap_tpl.h.

                                                   : _cmp_(compare) {
    _heap_.reserve(capacity);
 
    GUM_CONSTRUCTOR(Heap);
  }

References Heap(), _cmp_, _heap_, and capacity().

Referenced by Heap(), Heap(), Heap(), Heap(), ~Heap(), operator=(), and operator=().

Here is the call graph for this function:

Here is the caller graph for this function:

Heap() [2/4]

template<typename Val, typename Cmp>

gum::Heap< Val, Cmp >::Heap ( std::initializer_list< Val > list )

explicit

Initializer list constructor.

Parameters

list	The initializer list.

Definition at line 67 of file heap_tpl.h.

                                                        {
    _heap_.reserve(list.size());
    for (const auto& elt: list) {
      insert(elt);
    }
 
    GUM_CONSTRUCTOR(Heap);
  }

References Heap(), _heap_, and insert().

Here is the call graph for this function:

Heap() [3/4]

template<typename Val, typename Cmp>

gum::Heap< Val, Cmp >::Heap

(

const Heap< Val, Cmp > &

from

)

Copy constructor.

Parameters

from	The gum::Heap to copy.

Definition at line 78 of file heap_tpl.h.

                                                     :
      _heap_(from._heap_), _nb_elements_(from._nb_elements_), _cmp_(from._cmp_) {
    // for debugging purposes
    GUM_CONS_CPY(Heap);
  }

References Heap(), _cmp_, _heap_, and _nb_elements_.

Here is the call graph for this function:

Heap() [4/4]

template<typename Val, typename Cmp>

gum::Heap< Val, Cmp >::Heap ( Heap< Val, Cmp > && from )

noexcept

Move constructor.

Parameters

from	The gum::Heap to move.

Definition at line 86 of file heap_tpl.h.

                                                         :
      _heap_(std::move(from._heap_)), _nb_elements_(std::move(from._nb_elements_)),
      _cmp_(std::move(from._cmp_)) {
    // for debugging purposes
    GUM_CONS_MOV(Heap);
  }

References Heap(), _cmp_, _heap_, and _nb_elements_.

Here is the call graph for this function:

~Heap()

template<typename Val, typename Cmp>

gum::Heap< Val, Cmp >::~Heap

(

)

Class destructor.

Definition at line 95 of file heap_tpl.h.

                          {
    // for debugging purposes
    GUM_DESTRUCTOR(Heap);
  }

References Heap().

Here is the call graph for this function:

Member Function Documentation

_restoreHeap_()

template<typename Val, typename Cmp>

Size gum::Heap< Val, Cmp >::_restoreHeap_ ( )

private

After inserting an element at the end of the heap, restore heap property.

Definition at line 223 of file heap_tpl.h.

                                       {
    // get the element at the end of the heap
    Size i = _nb_elements_ - 1;
    Val  v = std::move(_heap_[i]);
 
    // restore the heap property
    for (Size j = (i - 1) >> 1; i && _cmp_(v, _heap_[j]); i = j, j = (j - 1) >> 1)
      _heap_[i] = std::move(_heap_[j]);
 
    _heap_[i] = std::move(v);
 
    return i;
  }

References _cmp_, _heap_, and _nb_elements_.

Referenced by emplace(), insert(), and insert().

Here is the caller graph for this function:

capacity()

template<typename Val, typename Cmp>

INLINE Size gum::Heap< Val, Cmp >::capacity ( ) const

noexcept

Returns the size of the internal structure storing the heap.

Returns

Returns the size of the internal structure storing the heap.

Definition at line 154 of file heap_tpl.h.

                                                        {
    return Size(_heap_.size());
  }

References _heap_.

Referenced by Heap().

Here is the caller graph for this function:

contains()

template<typename Val, typename Cmp>

INLINE bool gum::Heap< Val, Cmp >::contains

(

const Val &

val

)

const

Indicates whether the heap contains a given value.

Returns

Indicates whether the heap contains a given value.

Definition at line 273 of file heap_tpl.h.

                                                             {
    for (Size i = 0; i < _nb_elements_; ++i)
      if (_heap_[i] == val) return true;
 
    return false;
  }

References _heap_, and _nb_elements_.

emplace()

template<typename Val, typename Cmp>

template<typename... Args>

Size gum::Heap< Val, Cmp >::emplace

(

Args &&...

args

)

Emplace a new element in the heap and returns its index.

Template Parameters

Args	the type of the new element to emplace.

Parameters

args	The new element to emplace.

Returns

The emplaced element position in the gum::Heap.

Definition at line 258 of file heap_tpl.h.

                                               {
    // create a new element at the end of the heap
    _heap_.emplace_back(std::forward< Args >(args)...);
    ++_nb_elements_;
    return _restoreHeap_();
  }

References _heap_, _nb_elements_, and _restoreHeap_().

Here is the call graph for this function:

empty()

template<typename Val, typename Cmp>

INLINE bool gum::Heap< Val, Cmp >::empty ( ) const

noexcept

Indicates whether the heap is empty.

Returns

Indicates whether the heap is empty.

Definition at line 267 of file heap_tpl.h.

                                                     {
    return (_nb_elements_ == 0);
  }

References _nb_elements_.

erase()

template<typename Val, typename Cmp>

INLINE void gum::Heap< Val, Cmp >::erase

(

const Val &

val

)

Removes a given element from the heap (but does not return it).

If the element cannot be found, the function returns without throwing any exception.

Parameters

val	The element we wish to remove. If the heap contains several times this element, then the one with the smallest index is removed.

Definition at line 194 of file heap_tpl.h.

                                                    {
    // find val in the heap
    for (Size i = 0; i < _nb_elements_; ++i)
      if (_heap_[i] == val) {
        eraseByPos(i);
        break;
      }
  }

References _heap_, _nb_elements_, and eraseByPos().

Here is the call graph for this function:

eraseByPos()

template<typename Val, typename Cmp>

void gum::Heap< Val, Cmp >::eraseByPos

(

Size

index

)

Removes the element positioned at "index" from the heap.

If the element cannot be found, the function returns without throwing any exception.

Parameters

index

represents the position of the element to be removed. This is computed as follows: suppose that the heap is a complete binary tree, that is, a binary tree where all levels are completely filled except, maybe, the last one and, in this case, the elements of this level are all to the left of the tree. Then parsing the tree from top to bottom and, for each level, from left to right, and assigning index 0 to the root of the tree and, incrementing the index by 1 each time we jump to another node, we get a unique index for each element. This is precisely what the index passed in argument of the function represents.

index

The index of the element to remove

Definition at line 166 of file heap_tpl.h.

                                              {
    if (index >= _nb_elements_) return;
 
    // remove the element and put the last element in its place
    Val last = std::move(_heap_[_nb_elements_ - 1]);
    _heap_.pop_back();
    --_nb_elements_;
 
    if (!_nb_elements_ || (index == _nb_elements_)) return;
 
    // restore the heap property
    Size i = index;
 
    for (Size j = (index << 1) + 1; j < _nb_elements_; i = j, j = (j << 1) + 1) {
      // let j be the max child
      if ((j + 1 < _nb_elements_) && _cmp_(_heap_[j + 1], _heap_[j])) ++j;
 
      // if "last" is smaller than  _heap_[j], "last" must be stored at index i
      if (_cmp_(last, _heap_[j])) break;
 
      _heap_[i] = std::move(_heap_[j]);
    }
 
    _heap_[i] = std::move(last);
  }

References _cmp_, _heap_, and _nb_elements_.

Referenced by erase(), eraseTop(), and pop().

Here is the caller graph for this function:

eraseTop()

template<typename Val, typename Cmp>

INLINE void gum::Heap< Val, Cmp >::eraseTop

(

)

Removes the top of the heap (but does not return it).

If the heap is empty, it does nothing (in particular, it does not throw any exception).

Definition at line 205 of file heap_tpl.h.

                                         {
    // if the heap is empty, do nothing
    if (!_nb_elements_) return;
    eraseByPos(0);
  }

References _nb_elements_, and eraseByPos().

Here is the call graph for this function:

insert() [1/2]

template<typename Val, typename Cmp>

INLINE Size gum::Heap< Val, Cmp >::insert

(

const Val &

val

)

inserts a new element (actually a copy) in the heap and returns its index

Parameters

val	The element to insert.

Returns

The inserted element position in the gum::Heap.

Definition at line 239 of file heap_tpl.h.

                                                     {
    // create a new element at the end of the heap
    _heap_.push_back(val);
    ++_nb_elements_;
    return _restoreHeap_();
  }

References _heap_, _nb_elements_, and _restoreHeap_().

Referenced by Heap(), gum::learning::Miic::findBestContributor_(), and gum::learning::SimpleMiic::findBestContributor_().

Here is the call graph for this function:

Here is the caller graph for this function:

insert() [2/2]

template<typename Val, typename Cmp>

Size gum::Heap< Val, Cmp >::insert

(

Val &&

val

)

Inserts a new element (by moving it) in the heap and returns its index.

Parameters

val	The element to insert.

Returns

The inserted element position in the gum::Heap.

Definition at line 248 of file heap_tpl.h.

                                         {
    // create a new element at the end of the heap
    _heap_.push_back(std::move(val));
    ++_nb_elements_;
    return _restoreHeap_();
  }

References _heap_, _nb_elements_, and _restoreHeap_().

Here is the call graph for this function:

operator=() [1/2]

template<typename Val, typename Cmp>

Heap< Val, Cmp > & gum::Heap< Val, Cmp >::operator=

(

const Heap< Val, Cmp > &

from

)

Copy operator.

When a problem occurs during the copy (for instance when not enough memory is available), the operator guarantees that the heap stays in a coherent state. Actually, the heap becomes empty. An exception is then thrown.

Parameters

from	The gum::Heap to copy.

Definition at line 102 of file heap_tpl.h.

                                                                          {
    // avoid self assignment
    if (this != &from) {
      try {
        _heap_ = from._heap_;
      } catch (...) {
        _heap_.clear();
        _nb_elements_ = 0;
 
        throw;
      }
 
      // set the comparison function
      _cmp_         = from._cmp_;
      _nb_elements_ = from._nb_elements_;
 
      // for debugging purposes
      GUM_OP_CPY(Heap);
    }
 
    return *this;
  }

References Heap(), _cmp_, _heap_, and _nb_elements_.

Here is the call graph for this function:

operator=() [2/2]

template<typename Val, typename Cmp>

Heap< Val, Cmp > & gum::Heap< Val, Cmp >::operator= ( Heap< Val, Cmp > && from )

noexcept

Move operator.

When a problem occurs during the copy (for instance when not enough memory is available), the operator guarantees that the heap stays in a coherent state. Actually, the heap becomes empty. An exception is then thrown.

Parameters

from	The gum::Heap to move.

Definition at line 127 of file heap_tpl.h.

                                                                              {
    // avoid self assignment
    if (this != &from) {
      _heap_        = std::move(from._heap_);
      _nb_elements_ = std::move(from._nb_elements_);
      _cmp_         = std::move(from._cmp_);
    }
 
    return *this;
  }

References Heap(), _cmp_, _heap_, and _nb_elements_.

Here is the call graph for this function:

operator[]()

template<typename Val, typename Cmp>

INLINE const Val & gum::Heap< Val, Cmp >::operator[]

(

Size

index_elt

)

const

Returns the element at index index_elt from the heap.

Parameters

index_elt

The index of the element to return.

Returns

Returns the element at index index_elt from the heap.

Exceptions

NotFound

exception is thrown if there is no element at position "index_elt".

Definition at line 282 of file heap_tpl.h.

                                                                 {
    // check if the element exists
    if (index >= _nb_elements_) { GUM_ERROR(NotFound, "not enough elements in the heap") }
 
    return _heap_[index];
  }

References _heap_, _nb_elements_, and GUM_ERROR.

pop()

template<typename Val, typename Cmp>

INLINE Val gum::Heap< Val, Cmp >::pop

(

)

Removes the top element from the heap and return it.

Returns

Returns the top element from the heap.

Exceptions

NotFound

exception is thrown if the heap is empty.

Definition at line 213 of file heap_tpl.h.

                                   {
    if (!_nb_elements_) { GUM_ERROR(NotFound, "empty heap") }
 
    Val v = _heap_[0];
    eraseByPos(0);
    return v;
  }

References _heap_, _nb_elements_, eraseByPos(), and GUM_ERROR.

Referenced by gum::learning::Miic::iteration_(), and gum::learning::SimpleMiic::iteration_().

Here is the call graph for this function:

Here is the caller graph for this function:

resize()

template<typename Val, typename Cmp>

INLINE void gum::Heap< Val, Cmp >::resize

(

Size

new_size

)

Changes the size of the the internal structure storing the heap.

If the new size does not enable the heap to contain the elements it currently contains, then the resizing does not occur.

Parameters

new_size

The gum::Heap new size.

Definition at line 160 of file heap_tpl.h.

                                                    {
    if (new_size > _nb_elements_) _heap_.reserve(new_size);
  }

References _heap_, and _nb_elements_.

size()

template<typename Val, typename Cmp>

INLINE Size gum::Heap< Val, Cmp >::size ( ) const

noexcept

Returns the number of elements in the heap.

Returns

Returns the number of elements in the heap.

Definition at line 148 of file heap_tpl.h.

                                                    {
    return _nb_elements_;
  }

References _nb_elements_.

Referenced by gum::learning::Miic::iteration_(), and gum::learning::SimpleMiic::iteration_().

Here is the caller graph for this function:

top()

template<typename Val, typename Cmp>

INLINE const Val & gum::Heap< Val, Cmp >::top

(

)

const

Returns the element at the top of the heap.

Returns

Returns the element at the top of the heap.

Exceptions

NotFound

exception is thrown if the heap is empty.

Definition at line 140 of file heap_tpl.h.

                                                {
    if (!_nb_elements_) { GUM_ERROR(NotFound, "empty heap") }
 
    return _heap_[0];
  }

References _heap_, _nb_elements_, and GUM_ERROR.

Referenced by gum::learning::Miic::iteration_(), and gum::learning::SimpleMiic::iteration_().

Here is the caller graph for this function:

toString()

template<typename Val, typename Cmp>

std::string gum::Heap< Val, Cmp >::toString

(

)

const

Returns

Displays the content of the heap.

Returns a std::string representing the content of the heap.

Definition at line 291 of file heap_tpl.h.

                                             {
    bool              deja = false;
    std::stringstream stream;
    stream << "[";
 
    for (Size i = 0; i != _nb_elements_; ++i, deja = true) {
      if (deja) stream << " , ";
 
      stream << _heap_[i];
    }
 
    stream << "]";
 
    return stream.str();
  }

References _heap_, and _nb_elements_.

Referenced by gum::operator<<().

Here is the caller graph for this function:

Member Data Documentation

_cmp_

template<typename Val, typename Cmp = std::less< Val >>

Cmp gum::Heap< Val, Cmp >::_cmp_

private

Comparison function.

Definition at line 374 of file heap.h.

Referenced by Heap(), Heap(), Heap(), _restoreHeap_(), eraseByPos(), operator=(), and operator=().

_heap_

template<typename Val, typename Cmp = std::less< Val >>

std::vector< Val > gum::Heap< Val, Cmp >::_heap_

private

An array storing all the elements of the heap.

Definition at line 368 of file heap.h.

Referenced by Heap(), Heap(), Heap(), Heap(), _restoreHeap_(), capacity(), contains(), emplace(), erase(), eraseByPos(), insert(), insert(), operator=(), operator=(), operator[](), pop(), resize(), top(), and toString().

_nb_elements_

template<typename Val, typename Cmp = std::less< Val >>

Size gum::Heap< Val, Cmp >::_nb_elements_ {0}

private

The number of elements in the heap.

Definition at line 371 of file heap.h.

{0};

Referenced by Heap(), Heap(), _restoreHeap_(), contains(), emplace(), empty(), erase(), eraseByPos(), eraseTop(), insert(), insert(), operator=(), operator=(), operator[](), pop(), resize(), size(), top(), and toString().

---

The documentation for this class was generated from the following files:

• agrum/base/core/heap.h
• agrum/base/core/heap_tpl.h