ModErn Text Analysis
META Enumerates Textual Applications
Public Types | Public Member Functions | Private Attributes | List of all members
meta::util::fixed_heap< T, Comp > Class Template Reference

Keeps a constant number of high-priority elements. More...

#include <fixed_heap.h>

Public Types

using iterator = typename std::vector< T >::iterator
 
using const_iterator = typename std::vector< T >::const_iterator
 
using size_type = typename std::vector< T >::size_type
 

Public Member Functions

 fixed_heap (uint64_t max_elems, Comp comp)
 
void push (const T &elem)
 
template<class... Args>
void emplace (Args &&... args)
 
size_type size () const
 
size_type max_elems () const
 
std::vector< T > extract_top ()
 Clears the heap and returns the top elements. More...
 
const_iterator begin () const
 
const_iterator end () const
 

Private Attributes

uint64_t max_elems_
 
Comp comp_
 
std::vector< T > pq_
 

Detailed Description

template<class T, class Comp>
class meta::util::fixed_heap< T, Comp >

Keeps a constant number of high-priority elements.

This is useful for finding the "top-k" T elements using the comparison function Comp.

Internally, this class maintains a min-heap of max size max_elems, meaning that a push/emplace takes \(O(\log k)\) where \(k\) is max_elems passed on construction.

Your comparison function should be the same as you would pass to e.g. std::sort such that the result would be the elements in descending order.

Constructor & Destructor Documentation

§ fixed_heap()

template<class T , class Comp>
meta::util::fixed_heap< T, Comp >::fixed_heap ( uint64_t  max_elems,
Comp  comp 
)
Parameters
max_elems
compThe priority comparison function for elements in this heap

Member Function Documentation

§ push()

template<class T, class Comp >
void meta::util::fixed_heap< T, Comp >::push ( const T &  elem)
Parameters
elemThe element to insert; it may or may not be inserted depending on the size and priority of other elements in the heap

§ emplace()

template<class T , class Comp >
template<class... Args>
void meta::util::fixed_heap< T, Comp >::emplace ( Args &&...  args)
Parameters
elemThe element to emplace; it may or may not be inserted depending on the size and priority of other elements in the heap

§ size()

template<class T , class Comp >
auto meta::util::fixed_heap< T, Comp >::size ( ) const
Returns
the current number of elements in this heap; will always be less than or equal to max_elems()

§ max_elems()

template<class T , class Comp >
auto meta::util::fixed_heap< T, Comp >::max_elems ( ) const
Returns
the maximum number of elements this heap will store

§ extract_top()

template<class T , class Comp >
std::vector< T > meta::util::fixed_heap< T, Comp >::extract_top ( )

Clears the heap and returns the top elements.

Returns
the top elements in sorted order

§ begin()

template<class T , class Comp >
fixed_heap< T, Comp >::const_iterator meta::util::fixed_heap< T, Comp >::begin ( ) const
Returns
a const_iterator to the beginning of the fixed_heap
Note
the heap is not fully sorted

§ end()

template<class T , class Comp >
fixed_heap< T, Comp >::const_iterator meta::util::fixed_heap< T, Comp >::end ( ) const
Returns
a const_iterator to the end of the fixed_heap
Note
the heap is not fully sorted

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