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

Heap data structureThis structure is a basic heap data structure, i.e., it is a container in which elements are sorted according to a weak ordering. More...

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

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

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

Detailed Description

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

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.
Alloc	The allocator of elements stored in the gum::Heap.

Definition at line 47 of file heap.h.

Member Typedef Documentation

allocator_type

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

using gum::Heap< Val, Cmp, Alloc >::allocator_type = Alloc

Types for STL compliance.

Definition at line 132 of file heap.h.

const_pointer

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

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

Types for STL compliance.

Definition at line 129 of file heap.h.

const_reference

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

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

Types for STL compliance.

Definition at line 127 of file heap.h.

difference_type

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

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

Types for STL compliance.

Definition at line 131 of file heap.h.

pointer

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

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

Types for STL compliance.

Definition at line 128 of file heap.h.

reference

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

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

Types for STL compliance.

Definition at line 126 of file heap.h.

size_type

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

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

Types for STL compliance.

Definition at line 130 of file heap.h.

value_type

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

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

Types for STL compliance.

Definition at line 125 of file heap.h.

Constructor & Destructor Documentation

Heap() [1/5]

template<typename Val , typename Cmp , typename Alloc >

gum::Heap< Val, Cmp, Alloc >::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 38 of file heap_tpl.h.

                                                          : _cmp_(compare) {
    _heap_.reserve(capacity);

    GUM_CONSTRUCTOR(Heap);
  }

Heap() [2/5]

template<typename Val , typename Cmp , typename Alloc >

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

explicit

Initializer list constructor.

Parameters

list	The initializer list.

Definition at line 46 of file heap_tpl.h.

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

    GUM_CONSTRUCTOR(Heap);
  }

Heap() [3/5]

template<typename Val , typename Cmp , typename Alloc >

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

(

const Heap< Val, Cmp, Alloc > &

from

)

Copy constructor.

Parameters

from	The gum::Heap to copy.

Definition at line 57 of file heap_tpl.h.

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

Heap() [4/5]

template<typename Val , typename Cmp , typename Alloc >

template<typename OtherAlloc >

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

(

const Heap< Val, Cmp, OtherAlloc > &

from

)

Generalized copy constructor.

Template Parameters

OtherAlloc

The other gum::Heap allocator.

Parameters

from	The gum::Heap to copy.

Definition at line 66 of file heap_tpl.h.

                                                                        :
      _nb_elements_(from._nb_elements_), _cmp_(from._cmp_) {
    _heap_.reserve(_nb_elements_);

    // copy the elements of from. _heap_
    for (unsigned i = 0; i < _nb_elements_; ++i)
      _heap_.push_back(from._heap_[i]);

    // for debugging purposes
    GUM_CONS_CPY(Heap);
  }

Heap() [5/5]

template<typename Val , typename Cmp , typename Alloc >

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

noexcept

Move constructor.

Parameters

from	The gum::Heap to move.

Definition at line 80 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);
  }

~Heap()

template<typename Val , typename Cmp , typename Alloc >

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

(

)

Class destructor.

Definition at line 89 of file heap_tpl.h.

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

Member Function Documentation

_restoreHeap_()

template<typename Val , typename Cmp , typename Alloc >

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

private

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

Definition at line 249 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;
  }

capacity()

template<typename Val , typename Cmp , typename Alloc >

INLINE Size gum::Heap< Val, Cmp, Alloc >::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 180 of file heap_tpl.h.

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

contains()

template<typename Val , typename Cmp , typename Alloc >

INLINE bool gum::Heap< Val, Cmp, Alloc >::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 299 of file heap_tpl.h.

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

    return false;
  }

emplace()

template<typename Val , typename Cmp , typename Alloc >

template<typename... Args>

Size gum::Heap< Val, Cmp, Alloc >::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 284 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_();
  }

empty()

template<typename Val , typename Cmp , typename Alloc >

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

noexcept

Indicates whether the heap is empty.

Returns

Indicates whether the heap is empty.

Definition at line 293 of file heap_tpl.h.

                                                            {
    return (_nb_elements_ == 0);
  }

erase()

template<typename Val , typename Cmp , typename Alloc >

INLINE void gum::Heap< Val, Cmp, Alloc >::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 220 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;
      }
  }

eraseByPos()

template<typename Val , typename Cmp , typename Alloc >

void gum::Heap< Val, Cmp, Alloc >::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 192 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);
  }

eraseTop()

template<typename Val , typename Cmp , typename Alloc >

INLINE void gum::Heap< Val, Cmp, Alloc >::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 231 of file heap_tpl.h.

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

insert() [1/2]

template<typename Val , typename Cmp , typename Alloc >

INLINE Size gum::Heap< Val, Cmp, Alloc >::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 265 of file heap_tpl.h.

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

insert() [2/2]

template<typename Val , typename Cmp , typename Alloc >

Size gum::Heap< Val, Cmp, Alloc >::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 274 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_();
  }

operator=() [1/3]

template<typename Val , typename Cmp , typename Alloc >

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

(

const Heap< Val, Cmp, Alloc > &

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

operator=() [2/3]

template<typename Val , typename Cmp , typename Alloc >

template<typename OtherAlloc >

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

(

const Heap< Val, Cmp, OtherAlloc > &

from

)

Generalized 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.

Template Parameters

OtherAlloc

The other gum::Heap allocator.

Parameters

from	The gum::Heap to copy.

Definition at line 123 of file heap_tpl.h.

                                                                                {
    // avoid self assignment
    if (this != &from) {
      try {
        _heap_.clear();

        if (_heap_.capacity() < from._nb_elements_) _heap_.reserve(from._nb_elements_);

        for (unsigned int i = 0; i < from._nb_elements_; ++i) {
          _heap_.push_back(from._heap_[i]);
        }
      } catch (...) {
        _heap_.clear();
        _nb_elements_ = 0;
        throw;
      }

      _cmp_         = from._cmp_;
      _nb_elements_ = from._nb_elements_;

      // for debugging purposes
      GUM_OP_CPY(Heap);
    }

    return *this;
  }

operator=() [3/3]

template<typename Val , typename Cmp , typename Alloc >

Heap< Val, Cmp, Alloc > & gum::Heap< Val, Cmp, Alloc >::operator= ( Heap< Val, Cmp, Alloc > &&  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 153 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;
  }

operator[]()

template<typename Val , typename Cmp , typename Alloc >

INLINE const Val & gum::Heap< Val, Cmp, Alloc >::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 308 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];
  }

pop()

template<typename Val , typename Cmp , typename Alloc >

INLINE Val gum::Heap< Val, Cmp, Alloc >::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 239 of file heap_tpl.h.

                                          {
    if (!_nb_elements_) { GUM_ERROR(NotFound, "empty heap") }

    Val v = _heap_[0];
    eraseByPos(0);
    return v;
  }

resize()

template<typename Val , typename Cmp , typename Alloc >

INLINE void gum::Heap< Val, Cmp, Alloc >::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 186 of file heap_tpl.h.

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

size()

template<typename Val , typename Cmp , typename Alloc >

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

noexcept

Returns the number of elements in the heap.

Returns

Returns the number of elements in the heap.

Definition at line 174 of file heap_tpl.h.

                                                           {
    return _nb_elements_;
  }

top()

template<typename Val , typename Cmp , typename Alloc >

INLINE const Val & gum::Heap< Val, Cmp, Alloc >::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 166 of file heap_tpl.h.

                                                       {
    if (!_nb_elements_) { GUM_ERROR(NotFound, "empty heap") }

    return _heap_[0];
  }

toString()

template<typename Val , typename Cmp , typename Alloc >

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

(

)

const

Returns

Displays the content of the heap.

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

Definition at line 317 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();
  }

Member Data Documentation

_cmp_

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

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

private

Comparison function.

Definition at line 377 of file heap.h.

_heap_

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

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

private

An array storing all the elements of the heap.

Definition at line 371 of file heap.h.

_nb_elements_

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

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

private

The number of elements in the heap.

Definition at line 374 of file heap.h.

---

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

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