12 #ifndef TLX_CONTAINER_D_ARY_HEAP_HEADER
13 #define TLX_CONTAINER_D_ARY_HEAP_HEADER
35 template <
typename KeyType,
unsigned Arity = 2,
36 typename Compare = std::less<KeyType> >
39 static_assert(Arity,
"Arity must be greater than zero.");
45 static constexpr
size_t arity = Arity;
61 heap_.reserve(new_size);
78 size_t size() const noexcept {
return heap_.size(); }
89 heap_.push_back(new_key);
96 heap_.push_back(std::move(new_key));
128 template <
class InputIterator>
130 heap_.assign(first, last);
136 heap_.resize(keys.size());
137 std::copy(keys.begin(), keys.end(),
heap_.begin());
145 heap_ = std::move(keys);
155 std::queue<size_t> q;
159 size_t s = q.front();
162 for (
size_t i = 0; i <
arity && l <
heap_.size(); ++i) {
185 while (k > 0 && !
cmp_(
heap_[p], value)) {
189 heap_[k] = std::move(value);
198 if (l >=
heap_.size()) {
204 while (++l < right) {
220 heap_[k] = std::move(value);
225 if (
heap_.size() >= 2) {
227 size_t last_internal = (
heap_.size() - 2) /
arity;
228 for (
size_t i = last_internal + 1; i; --i) {
234 size_t l =
left(cur);
237 for (
size_t j = l + 1;
251 }
while (cur <= last_internal);
252 heap_[cur] = std::move(value);
259 template <
typename KeyType,
unsigned Arity = 2,
260 typename Compare = std::less<KeyType> >
This class implements a d-ary comparison-based heap usable as a priority queue.
DAryHeap(DAryHeap &&)=default
Move.
void build_heap(std::vector< key_type > &&keys)
Builds a heap from the vector keys. Items of keys are moved.
static constexpr size_t arity
bool sanity_check()
For debugging: runs a BFS from the root node and verifies that the heap property is respected.
size_t capacity() const noexcept
Returns the capacity of the heap.
const key_type & top() const noexcept
Returns the top item.
void pop()
Removes the top item.
void sift_up(size_t k)
Pushes the node at position k up until either it becomes the root or its parent has lower or equal pr...
size_t parent(size_t k) const
Returns the position of the parent of the node at position k.
size_t size() const noexcept
Returns the number of items in the heap.
bool empty() const noexcept
Returns true if the heap has no items, false otherwise.
key_type extract_top()
Removes and returns the top item.
void build_heap(const std::vector< key_type > &keys)
Builds a heap from the vector keys. Items of keys are copied.
void build_heap(InputIterator first, InputIterator last)
Builds a heap from a container.
void reserve(size_t new_size)
Allocates space for new_size items.
size_t left(size_t k) const
Returns the position of the left child of the node at position k.
void update_all()
Rebuilds the heap.
compare_type cmp_
Compare function.
void heapify()
Reorganize heap_ into a heap.
DAryHeap(const DAryHeap &)=default
Copy.
DAryHeap & operator=(const DAryHeap &)=default
void push(key_type &&new_key)
Inserts a new item.
void push(const key_type &new_key)
Inserts a new item.
void clear()
Empties the heap.
std::vector< key_type > heap_
Cells in the heap.
void sift_down(size_t k)
Pushes the item at position k down until either it becomes a leaf or all its children have higher pri...
DAryHeap(compare_type cmp=compare_type())
Allocates an empty heap.
static uint32_t min(uint32_t x, uint32_t y)
void swap(CountingPtr< A, D > &a1, CountingPtr< A, D > &a2) noexcept
swap enclosed object with another counting pointer (no reference counts need change)