Thrill  0.1
Public Types | Private Attributes | List of all members
BinaryHeap< Type, Compare > Class Template Reference

Detailed Description

template<typename Type, typename Compare = std::less<Type>>
class thrill::common::BinaryHeap< Type, Compare >

A simple binary heap priority queue, except that one can additionally find and delete arbitrary items in O(n).

Definition at line 31 of file binary_heap.hpp.

+ Inheritance diagram for BinaryHeap< Type, Compare >:

#include <binary_heap.hpp>

Public Types

using const_reference = const Type &
 
using Container = std::vector< Type >
 
using difference_type = typename Container::difference_type
 
using size_type = size_t
 
using value_type = Type
 

Public Member Functions

PQ Interface
 BinaryHeap (const Compare &cmp=Compare())
 
bool empty () const
 check if PQ is empty More...
 
size_type size () const
 return number of items in the PQ More...
 
const_reference top () const
 return reference to top item in PQ More...
 
template<typename... Args>
void emplace (Args &&... args)
 add an items in the PQ. More...
 
void pop ()
 remove the top item in the PQ More...
 
Additional Methods
Container & container ()
 direct access to heap container More...
 
template<typename Functor >
size_t erase (Functor &&f)
 

Static Public Member Functions

Free Binary Heap Methods
template<typename Iterator >
static void sift_up (Iterator first, Iterator last, const Compare &comp, difference_type len)
 
template<typename Iterator >
static void push_heap (Iterator first, Iterator last, const Compare &comp)
 
template<typename Iterator >
static void sift_down (Iterator first, Iterator, const Compare &comp, difference_type len, Iterator start)
 
template<typename Iterator >
static void pop_heap (Iterator first, Iterator last, const Compare &comp, difference_type len)
 
template<typename Iterator >
static void pop_heap (Iterator first, Iterator last, const Compare &comp)
 

Private Attributes

Container c_
 array holding binary heap More...
 
Compare cmp_
 compare More...
 

Member Typedef Documentation

◆ const_reference

using const_reference = const Type&

Definition at line 36 of file binary_heap.hpp.

◆ Container

using Container = std::vector<Type>

Definition at line 34 of file binary_heap.hpp.

◆ difference_type

using difference_type = typename Container::difference_type

Definition at line 38 of file binary_heap.hpp.

◆ size_type

using size_type = size_t

Definition at line 37 of file binary_heap.hpp.

◆ value_type

using value_type = Type

Definition at line 35 of file binary_heap.hpp.

Constructor & Destructor Documentation

◆ BinaryHeap()

BinaryHeap ( const Compare &  cmp = Compare())
inlineexplicit

Definition at line 43 of file binary_heap.hpp.

Member Function Documentation

◆ container()

Container& container ( )
inline

direct access to heap container

Definition at line 74 of file binary_heap.hpp.

Referenced by ProfileThread::~ProfileThread().

◆ emplace()

void emplace ( Args &&...  args)
inline

add an items in the PQ.

Definition at line 57 of file binary_heap.hpp.

Referenced by ProfileThread::Add(), and ProfileThread::Worker().

◆ empty()

bool empty ( ) const
inline

check if PQ is empty

Definition at line 47 of file binary_heap.hpp.

Referenced by ProfileThread::Worker().

◆ erase()

size_t erase ( Functor &&  f)
inline

iterate over all items, delete those for which f returns true. Takes time O(n). If you need to erase items frequently, use a different PQ.

Definition at line 79 of file binary_heap.hpp.

Referenced by ProfileThread::Remove().

◆ pop()

void pop ( )
inline

remove the top item in the PQ

Definition at line 63 of file binary_heap.hpp.

Referenced by ProfileThread::Worker().

◆ pop_heap() [1/2]

static void pop_heap ( Iterator  first,
Iterator  last,
const Compare &  comp,
difference_type  len 
)
inlinestatic

Definition at line 178 of file binary_heap.hpp.

Referenced by BinaryHeap< Timer >::pop(), and BinaryHeap< Timer >::pop_heap().

◆ pop_heap() [2/2]

static void pop_heap ( Iterator  first,
Iterator  last,
const Compare &  comp 
)
inlinestatic

Definition at line 188 of file binary_heap.hpp.

◆ push_heap()

static void push_heap ( Iterator  first,
Iterator  last,
const Compare &  comp 
)
inlinestatic

Definition at line 127 of file binary_heap.hpp.

Referenced by BinaryHeap< Timer >::emplace().

◆ sift_down()

static void sift_down ( Iterator  first,
Iterator  ,
const Compare &  comp,
difference_type  len,
Iterator  start 
)
inlinestatic

Definition at line 132 of file binary_heap.hpp.

Referenced by BinaryHeap< Timer >::erase(), and BinaryHeap< Timer >::pop_heap().

◆ sift_up()

static void sift_up ( Iterator  first,
Iterator  last,
const Compare &  comp,
difference_type  len 
)
inlinestatic

Definition at line 103 of file binary_heap.hpp.

Referenced by BinaryHeap< Timer >::push_heap().

◆ size()

size_type size ( ) const
inline

return number of items in the PQ

Definition at line 50 of file binary_heap.hpp.

◆ top()

const_reference top ( ) const
inline

return reference to top item in PQ

Definition at line 53 of file binary_heap.hpp.

Referenced by BinaryHeap< Timer >::sift_down(), and ProfileThread::Worker().

Member Data Documentation

◆ c_

Container c_
private

array holding binary heap

Definition at line 196 of file binary_heap.hpp.

Referenced by BinaryHeap< Timer >::container(), BinaryHeap< Timer >::emplace(), BinaryHeap< Timer >::empty(), BinaryHeap< Timer >::erase(), BinaryHeap< Timer >::pop(), BinaryHeap< Timer >::size(), and BinaryHeap< Timer >::top().

◆ cmp_

Compare cmp_
private

compare

Definition at line 199 of file binary_heap.hpp.

Referenced by BinaryHeap< Timer >::emplace(), BinaryHeap< Timer >::erase(), and BinaryHeap< Timer >::pop().

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