48 heap_ptr() : recptr(NULL), run_id(0) {};
49 heap_ptr(
const REC * a,
size_t b) : recptr(a), run_id(b) {};
58 template<
class REC,
class comp_t=std::less<REC> >
61 struct comp:
public std::binary_function<heap_ptr<REC>, heap_ptr<REC>, bool> {
63 comp(comp_t & _): c(_) {}
65 return c(*a.recptr, *b.recptr);
101 run_id=*pq.top().run_id();
119 inline void delete_min_and_insert(
const REC *nextelement_same_run) {
120 if (nextelement_same_run)
121 pq.pop_and_push(
heap_ptr<REC>(nextelement_same_run, pq.top().run_id));
129 inline size_t space_per_item() {
return static_cast<size_t>(pq.memory_coefficient()); }
134 inline size_t space_overhead() {
return static_cast<size_t>(pq.memory_overhead()); }
140 template<
class REC,
class CMPR>
165 template<
class REC,
class comp_t=std::less<REC> >
168 struct comp:
public std::binary_function<heap_element<REC>, heap_element<REC>, bool> {
170 comp(comp_t & _): c(_) {}
172 return c(a.key, b.key);
208 run_id=pq.top().run_id;
226 inline void delete_min_and_insert(
const REC *nextelement_same_run) {
227 if (nextelement_same_run)
236 inline size_t space_per_item(
void) {
return static_cast<size_t>(pq.memory_coefficient());}
241 inline size_t space_overhead(
void) {
return static_cast<size_t>(pq.memory_overhead());}
248 template<
class REC,
class Compare>
258 #endif // _MERGE_HEAP_H
size_t sizeofheap()
Reports the size of Heap (number of elements).
Memory management subsystem.
void deallocate()
Deallocates the space used by the heap.
size_t space_per_item()
Returns the main memory space usage per item.
size_t space_per_item(void)
Returns the main memory space usage per item.
void initialize(void)
Heapifies an initial array of elements.
void initialize()
Heapifies an initial array of elements;.
This file contains a few deprecated definitions for legacy code.
size_t space_overhead(void)
Returns the fixed main memory space overhead, regardless of item count.
Standard binary internal heap.
Simple heap based priority queue implementation.
size_t space_overhead()
Returns the fixed main memory space overhead, regardless of item count.
A record pointer heap that uses a comparison object.
A merge heap object base class - also serves as the full implementation for objects with a < comparis...
A record pointer heap base class - also serves as the full implementation for objects with a < compar...
void insert(const REC *ptr, size_t run_id)
Copies an (initial) element into the heap array.
size_t get_min_run_id()
Returns the run with the minimum key.
This is a record pointer element.
size_t get_min_run_id()
Returns the run with the minimum key.
void allocate(size_t size)
Allocates space for the heap.
size_t sizeofheap()
Reports the size of Heap (number of elements).
void insert(const REC *ptr, size_t run_id)
Copies an (initial) element into the heap array/.
void deallocate()
Deallocates the space used by the heap.
void allocate(size_t size)
Allocates space for the heap.
void extract_min(REC &el, size_t &run_id)
Extracts minimum element from heap array.
void extract_min(REC &el, size_t &run_id)
Extracts minimum element from heap array.