12#ifndef TLX_CONTAINER_D_ARY_ADDRESSABLE_INT_HEAP_HEADER
13#define TLX_CONTAINER_D_ARY_ADDRESSABLE_INT_HEAP_HEADER
39template <
typename KeyType,
unsigned Arity = 2,
40 class Compare = std::less<KeyType> >
43 static_assert(std::numeric_limits<KeyType>::is_integer &&
44 !std::numeric_limits<KeyType>::is_signed,
45 "KeyType must be an unsigned integer type.");
46 static_assert(Arity,
"Arity must be greater than zero.");
52 static constexpr size_t arity = Arity;
78 heap_.reserve(new_size);
97 size_t size() const noexcept {
return heap_.size(); }
118 heap_.push_back(new_key);
135 heap_.push_back(std::move(new_key));
206 template <
class InputIterator>
208 heap_.assign(first, last);
214 heap_.resize(keys.size());
215 std::copy(keys.begin(), keys.end(),
heap_.begin());
223 heap_ = std::move(keys);
233 std::vector<unsigned char> mark(
handles_.size());
234 std::queue<size_t> q;
238 mark.at(
heap_[0]) = 1;
240 size_t s = q.front();
243 for (
size_t i = 0; i <
arity && l <
heap_.size(); ++i) {
252 mark.at(
heap_[l]) = 1;
257 for (
size_t i = 0; i < mark.size(); ++i) {
276 while (k > 0 && !
cmp_(
heap_[p], value)) {
282 heap_[k] = std::move(value);
291 if (l >=
heap_.size()) {
296 size_t right = std::min(
heap_.size(), c +
arity);
297 while (++l < right) {
315 heap_[k] = std::move(value);
321 if (
heap_.size() >= 2) {
323 size_t last_internal = (
heap_.size() - 2) /
arity;
324 for (
size_t i = last_internal + 1; i; --i) {
328 max_key = std::max(max_key, value);
331 size_t l =
left(cur);
332 max_key = std::max(max_key,
heap_[l]);
335 for (
size_t j = l + 1;
339 max_key = std::max(max_key,
heap_[j]);
350 }
while (cur <= last_internal);
351 heap_[cur] = std::move(value);
356 for (
size_t i = 0; i <
heap_.size(); ++i)
362template <
typename KeyType,
unsigned Arity = 2,
363 typename Compare = std::less<KeyType> >
This class implements an addressable integer priority queue, precisely a d-ary heap.
void build_heap(std::vector< key_type > &&keys)
Builds a heap from the vector keys. Items of keys are moved.
static constexpr key_type not_present()
Marks a key that is not in the heap.
DAryAddressableIntHeap(compare_type cmp=compare_type())
Allocates an empty heap.
static constexpr size_t arity
DAryAddressableIntHeap(const DAryAddressableIntHeap &)=default
Copy.
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.
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 remove(key_type key)
Removes the item with key key.
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.
void heapify()
Reorganize heap_ into a heap.
DAryAddressableIntHeap(DAryAddressableIntHeap &&)=default
Move.
void update(key_type key)
Updates the priority queue after the priority associated to the item with key key has been changed; i...
bool contains(key_type key) const
Returns true if the key key is in the heap, false otherwise.
void push(key_type &&new_key)
Inserts a new item.
std::vector< key_type > handles_
void push(const key_type &new_key)
Inserts a new item.
const key_type & top() const noexcept
Returns the top item.
void clear()
Empties the heap.
DAryAddressableIntHeap & operator=(const DAryAddressableIntHeap &)=default
std::vector< key_type > 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...
DAryAddressableIntHeap< KeyType, Arity, Compare > d_ary_addressable_int_heap
make template alias due to similarity with std::priority_queue