alglib::heap::binary_heap< elt_t, key_t > Class Template Reference

#include <binary_heap.h>

Inheritance diagram for alglib::heap::binary_heap< elt_t, key_t >:

Public Types
typedef elt_t	elt_type
typedef key_t	key_type

Public Member Functions
	binary_heap ()
template<typename InputIter >
	binary_heap (InputIter elt_first, InputIter elt_last, InputIter key_first)
void	insert (const elt_t &elt, const key_t &key)
const elt_t &	get_min_elt () const
const key_t &	get_min_key () const
void	delete_min ()
void	replace (const elt_t &elt, const key_t &key)
int	size () const override
bool	empty () const override
void	update_key (const elt_t &elt, const key_t &key)

Member Typedef Documentation

template<typename elt_t, typename key_t>

typedef elt_t alglib::heap::binary_heap< elt_t, key_t >::elt_type

template<typename elt_t, typename key_t>

typedef key_t alglib::heap::binary_heap< elt_t, key_t >::key_type

Constructor & Destructor Documentation

template<typename elt_t , typename key_t >

alglib::heap::binary_heap< elt_t, key_t >::binary_heap

(

)

                                       {
    __sz = 0;
}

template<typename elt_t , typename key_t >

template<typename InputIter >

alglib::heap::binary_heap< elt_t, key_t >::binary_heap ( InputIter  elt_first, InputIter  elt_last, InputIter  key_first  )

explicit

                                                            {
    __sz = 0;
    while (elt_first != elt_last) {
        auto loc = make_entry(*elt_first);
        heaparr[__sz++] = node_t {*key_first, loc};
        ++elt_first;
    }

    // Heapify the __stash
    for (int i = __sz / 2; i >= 0; i--)
         __sift_down(i);
}

Member Function Documentation

template<typename elt_t , typename key_t >

void alglib::heap::binary_heap< elt_t, key_t >::delete_min ( )

virtual

Implements alglib::heap::min_heap< elt_t, key_t >.

                                           {
    nodeof.erase(heaparr[0].elt_it);
    std::swap(heaparr[0], heaparr[__sz - 1]);
    --__sz;
    __sift_down(0);
}

template<typename elt_t, typename key_t>

bool alglib::heap::binary_heap< elt_t, key_t >::empty ( ) const

inlineoverridevirtual

Implements alglib::heap::min_heap< elt_t, key_t >.

{ return __sz == 0; }

template<typename elt_t , typename key_t >

const elt_t & alglib::heap::binary_heap< elt_t, key_t >::get_min_elt ( ) const

virtual

Implements alglib::heap::min_heap< elt_t, key_t >.

                                                          {
    return (heaparr[0].elt_it)->first;
}

template<typename elt_t , typename key_t >

const key_t & alglib::heap::binary_heap< elt_t, key_t >::get_min_key ( ) const

virtual

Implements alglib::heap::min_heap< elt_t, key_t >.

                                                          {
    return heaparr[0].key;
}

template<typename elt_t, typename key_t>

void alglib::heap::binary_heap< elt_t, key_t >::insert ( const elt_t &  elt, const key_t &  key  )

virtual

Implements alglib::heap::min_heap< elt_t, key_t >.

                                                         {
    auto loc = make_entry(elt);
    heaparr.push_back(node_t {key, loc});
    __sift_up(__sz);
    ++__sz;
}

template<typename elt_t, typename key_t>

void alglib::heap::binary_heap< elt_t, key_t >::replace ( const elt_t &  elt, const key_t &  key  )

virtual

Implements alglib::heap::min_heap< elt_t, key_t >.

                                                          {
    if (__sz == 0)
        throw std::underflow_error("Empty heap");
    auto loc = make_entry(elt);
    nodeof.erase(heaparr[0].elt_it);  // Clean up the elt from nodeof map
    heaparr[0] = node_t {key, loc};
    __sift_down(0);
}

template<typename elt_t, typename key_t>

int alglib::heap::binary_heap< elt_t, key_t >::size ( ) const

inlineoverridevirtual

Implements alglib::heap::min_heap< elt_t, key_t >.

{ return __sz; }

template<typename elt_t, typename key_t>

void alglib::heap::binary_heap< elt_t, key_t >::update_key ( const elt_t &  elt, const key_t &  key  )

virtual

Implements alglib::heap::min_heap< elt_t, key_t >.

                                                             {
    if (nodeof.find(elt) == nodeof.end())
        throw std::domain_error("The element doesn't exist");
    int index_in_heap = nodeof[elt];
    heaparr[index_in_heap] = node_t {key, heaparr[index_in_heap].elt_it};
    __sift_up(index_in_heap);
    __sift_down(index_in_heap);
}

---

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

• alglib/heap/binary_heap.h