This class implements a monotonic integer min priority queue, more specific a multi-level radix heap.
Here, monotonic refers to the fact that the heap maintains an insertion limit and does not allow the insertion of keys smaller than this limit. The frontier is increased to the current minimum when invoking the methods top(), pop() and swap_top_bucket(). To query the currently smallest item without updating the insertion limit use peak_top_key().
We implement a two level radix heap. Let k=sizeof(KeyType)*8 be the number of bits in a key. In contrast to an ordinary radix heap which contains k buckets, we maintain ceil(k/log2(Radix)) rows each containing Radix-many buckets. This reduces the number of move operations when reorganizing the data structure.
Radix A power of two <= 64.
Definition at line 376 of file radix_heap.hpp.
Definition at line 402 of file radix_heap.hpp.
Definition at line 386 of file radix_heap.hpp.
Definition at line 394 of file radix_heap.hpp.
Definition at line 391 of file radix_heap.hpp.
Definition at line 384 of file radix_heap.hpp.
Definition at line 392 of file radix_heap.hpp.
Definition at line 385 of file radix_heap.hpp.
Definition at line 404 of file radix_heap.hpp.
Clears all internal queues and resets insertion limit.
Definition at line 545 of file radix_heap.hpp.
Construct and insert element with priority key.
In contrast to all other methods the key has to be provided explicitly as the first argument. All other arguments are passed to the constructor of the element.
Definition at line 433 of file radix_heap.hpp.
Definition at line 454 of file radix_heap.hpp.
In case the first parameter can be directly casted into key_type, using this method avoid repeating it.
Definition at line 445 of file radix_heap.hpp.
Indicates whether size() == 0.
Definition at line 497 of file radix_heap.hpp.
Definition at line 417 of file radix_heap.hpp.
Definition at line 421 of file radix_heap.hpp.
Definition at line 563 of file radix_heap.hpp.
Returns currently smallest key without updating the insertion limit.
Definition at line 507 of file radix_heap.hpp.
Definition at line 522 of file radix_heap.hpp.
Insert element with priority key.
Definition at line 467 of file radix_heap.hpp.
Definition at line 482 of file radix_heap.hpp.
Definition at line 574 of file radix_heap.hpp.
Returns number of elements currently stored.
Definition at line 502 of file radix_heap.hpp.
Exchanges the top buckets with an empty user provided bucket.
Definition at line 534 of file radix_heap.hpp.
Returns currently smallest key and data.
Definition at line 515 of file radix_heap.hpp.
Definition at line 556 of file radix_heap.hpp.
Definition at line 558 of file radix_heap.hpp.
Definition at line 554 of file radix_heap.hpp.
Definition at line 381 of file radix_heap.hpp.
Definition at line 561 of file radix_heap.hpp.
Definition at line 553 of file radix_heap.hpp.
Definition at line 551 of file radix_heap.hpp.
Definition at line 560 of file radix_heap.hpp.
Definition at line 399 of file radix_heap.hpp.
Definition at line 397 of file radix_heap.hpp.
Definition at line 388 of file radix_heap.hpp.
Definition at line 396 of file radix_heap.hpp.
Definition at line 552 of file radix_heap.hpp.