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;
50 template <
typename IT>
52 comp_t c=comp_t()): pq(max_size), sz(0), comp(c) {
59 template <
typename IT>
60 void insert(
const IT & start,
const IT & end) {
61 std::copy(start, end, pq.
find(sz));
81 std::make_heap(pq.
begin(), pq.
find(sz), comp);
88 bool empty()
const {
return sz == 0;}
94 inline size_type
size()
const {
return sz;}
101 inline void push(
const T & v) {
104 std::push_heap(pq.begin(), pq.find(sz), comp);
112 std::pop_heap(pq.
begin(), pq.
find(sz), comp);
130 inline const T &
top()
const {
return pq[0];}
174 #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())
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.
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.
void resize(size_t size, const T &elm)
Change the size of the array.
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.
internal_priority_queue(size_type max_size, comp_t c=comp_t())
Construct a priority queue.