20 #ifndef __TPIE_INTERNAL_PRIORITY_QUEUE_H__
21 #define __TPIE_INTERNAL_PRIORITY_QUEUE_H__
36 template <
typename T,
typename comp_t = std::less<T> >
39 typedef memory_size_type size_type;
47 : pq(max_size, bucket), sz(0), comp(c) {}
52 template <
typename IT>
56 : pq(max_size, bucket), sz(0), comp(c) {
63 template <
typename IT>
64 void insert(
const IT & start,
const IT & end) {
65 std::copy(start, end, pq.
find(sz));
81 pq[sz++] = std::move(v);
89 std::make_heap(pq.
begin(), pq.
find(sz), comp);
96 bool empty()
const {
return sz == 0;}
102 size_type
size()
const {
return sz;}
112 std::push_heap(pq.begin(), pq.find(sz), comp);
117 pq[sz++] = std::move(v);
118 std::push_heap(pq.begin(), pq.find(sz), comp);
126 std::pop_heap(pq.begin(), pq.find(sz), comp);
141 pq[0] = std::move(v);
150 const T &
top()
const {
return pq[0];}
152 T &
top() {
return pq[0];}
188 void resize(
size_t s) {sz=0; pq.resize(s);}
196 #endif //__TPIE_INTERNAL_PRIORITY_QUEUE_H__
tpie::array< T > & get_array()
Return the underlying array.
void pop_and_push_heap(T a, T b, C lt)
Restore heap invariants after the first element has been replaced by some other element.
iterator find(size_t idx)
Return an iterator to the i'th element of the array.
void push(const T &v)
Insert an element into the priority queue.
Base class of data structures with linear memory usage.
size_type size() const
Returns the size of the queue.
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.
static double memory_overhead()
Return the memory overhead of the structure.
Standard binary internal heap.
bool empty() const
Is the queue empty?
Generic internal array with known memory requirements.
void pop()
Remove the minimum element from heap.
internal_priority_queue(size_type max_size, comp_t c=comp_t(), memory_bucket_ref bucket=memory_bucket_ref())
Construct a priority queue.
Class storring a reference to a memory bucket.
void pop_and_push(const T &v)
Remove the minimum element and insert a new element.
void resize(size_t s)
Resize priority queue to given size.
Miscellaneous utility functions.
static double memory_coefficient()
Return the memory coefficient of the structure.
void clear()
Clear the structure of all elements.
const T & top() const
Return the minimum element.
static double memory_overhead()
Return the memory overhead of the structure.
void insert(const IT &start, const IT &end)
Insert some elements and run make_heap.
static double memory_coefficient()
Return the memory coefficient of the structure.
iterator begin()
Return an iterator to the beginning of the array.
size_type size() const
Return the size of the array.
void unsafe_push(const T &v)
Insert an element into the priority queue, possibly destroying ordering information.
void make_safe()
Make the priority queue safe after a sequence of calls to unsafe_push.