Expand description
A priority queue implemented with a weak heap.
Insertion and popping the largest element have O(log(n)) time complexity. Checking the largest element is O(1). Converting a vector to a weak heap can be done in-place, and has O(n) complexity. A weak heap can also be converted to a sorted vector in-place, allowing it to be used for an O(n * log(n)) in-place weak-heapsort.
The main purpose of using a weak heap is to minimize the number of comparisons
required for push and pop operations or sorting, which is why it is especially
useful in cases where comparing elements is an expensive operation, for example, string collation.
For the classical comparison of numbers, it is still preferable to use a standard binary heap,
since operations with a weak heap require additional numerical operations compared
to a conventional binary heap.
This create presents an implementation of the weak heap - WeakHeap, which has an identical interface
with BinaryHeap
from std::collections, and at the same time it has several new useful methods.
Read about weak heap:
Structs
A draining iterator over the elements of a WeakHeap.
An owning iterator over the elements of a WeakHeap.
An iterator over the elements of a WeakHeap.
A priority queue implemented with a weak heap.
Structure wrapping a mutable reference to the greatest item on a
WeakHeap.