Standard binary internal heap. More...
#include <tpie/internal_priority_queue.h>
Inherits tpie::linear_memory_base< internal_priority_queue< T, comp_t > >.
Public Types | |
typedef memory_size_type | size_type |
Public Member Functions | |
internal_priority_queue (size_type max_size, comp_t c=comp_t(), memory_bucket_ref bucket=memory_bucket_ref()) | |
Construct a priority queue. More... | |
template<typename IT > | |
internal_priority_queue (size_type max_size, const IT &start, const IT &end, comp_t c=comp_t(), memory_bucket_ref bucket=memory_bucket_ref()) | |
Construct a priority queue with given elements. More... | |
template<typename IT > | |
void | insert (const IT &start, const IT &end) |
Insert some elements and run make_heap. More... | |
void | unsafe_push (const T &v) |
Insert an element into the priority queue, possibly destroying ordering information. More... | |
void | unsafe_push (T &&v) |
void | make_safe () |
Make the priority queue safe after a sequence of calls to unsafe_push. More... | |
bool | empty () const |
Is the queue empty? More... | |
size_type | size () const |
Returns the size of the queue. More... | |
void | push (const T &v) |
Insert an element into the priority queue. More... | |
void | push (T &&v) |
void | pop () |
Remove the minimum element from heap. More... | |
void | pop_and_push (const T &v) |
Remove the minimum element and insert a new element. More... | |
void | pop_and_push (T &&v) |
const T & | top () const |
Return the minimum element. More... | |
T & | top () |
tpie::array< T > & | get_array () |
Return the underlying array. More... | |
void | clear () |
Clear the structure of all elements. More... | |
void | resize (size_t s) |
Resize priority queue to given size. More... | |
Static Public Member Functions | |
static double | memory_coefficient () |
Return the memory coefficient of the structure. More... | |
static double | memory_overhead () |
Return the memory overhead of the structure. More... | |
static memory_size_type | memory_usage (memory_size_type size) |
Return the number of bytes required to create a data structure supporting a given number of elements. More... | |
static memory_size_type | memory_fits (memory_size_type memory) |
Return the maximum number of elements that can be contained in in the structure when it is allowed to fill a given number of bytes. More... | |
Standard binary internal heap.
Definition at line 37 of file internal_priority_queue.h.
|
inline |
Construct a priority queue.
max_size | Maximum size of queue. |
Definition at line 45 of file internal_priority_queue.h.
|
inline |
Construct a priority queue with given elements.
Definition at line 53 of file internal_priority_queue.h.
|
inline |
Clear the structure of all elements.
Definition at line 182 of file internal_priority_queue.h.
|
inline |
Is the queue empty?
Definition at line 96 of file internal_priority_queue.h.
Referenced by tpie::internal_priority_queue< tpie::ami::heap_ptr< REC >, comp >::pop(), and tpie::internal_priority_queue< tpie::ami::heap_ptr< REC >, comp >::pop_and_push().
|
inline |
Return the underlying array.
Make sure you know what you are doing.
Definition at line 175 of file internal_priority_queue.h.
|
inline |
Insert some elements and run make_heap.
Definition at line 64 of file internal_priority_queue.h.
Referenced by tpie::internal_priority_queue< tpie::ami::heap_ptr< REC >, comp >::internal_priority_queue().
|
inline |
Make the priority queue safe after a sequence of calls to unsafe_push.
Definition at line 88 of file internal_priority_queue.h.
Referenced by tpie::internal_priority_queue< tpie::ami::heap_ptr< REC >, comp >::insert().
|
inlinestatic |
Return the memory coefficient of the structure.
Allocating a structure with n elements will use at most bytes. This does not include memory overhead incurred if the structure is allocated using new.
Definition at line 158 of file internal_priority_queue.h.
|
inlinestaticinherited |
Return the maximum number of elements that can be contained in in the structure when it is allowed to fill a given number of bytes.
memory | The number of bytes the structure is allowed to occupy |
|
inlinestatic |
Return the memory overhead of the structure.
Definition at line 166 of file internal_priority_queue.h.
|
inlinestaticinherited |
Return the number of bytes required to create a data structure supporting a given number of elements.
size | The number of elements to support |
|
inline |
Remove the minimum element from heap.
Definition at line 124 of file internal_priority_queue.h.
|
inline |
Remove the minimum element and insert a new element.
Definition at line 133 of file internal_priority_queue.h.
|
inline |
Insert an element into the priority queue.
v | The element that should be inserted. |
Definition at line 109 of file internal_priority_queue.h.
|
inline |
Resize priority queue to given size.
s | New size of priority queue. |
Definition at line 188 of file internal_priority_queue.h.
|
inline |
Returns the size of the queue.
Definition at line 102 of file internal_priority_queue.h.
Referenced by tpie::internal_priority_queue< tpie::ami::heap_ptr< REC >, comp >::push().
|
inline |
Return the minimum element.
Definition at line 150 of file internal_priority_queue.h.
|
inline |
Insert an element into the priority queue, possibly destroying ordering information.
v | The element that should be inserted. |
Definition at line 76 of file internal_priority_queue.h.