We introduce a relaxed weak queue, a priority queue that is
visualized and demonstrated as a collection of binary trees
(not multiary trees). It supports all priorityqueue operations as
efficiently as a runrelaxed heap: findmin, insert, and
decrease in O(1) worstcase time, and delete in O(lg n)
worstcase time, n denoting the number of elements stored prior to
the operation. A relaxed weak queue uses 3n + O(lg n) pointers
besides the space used to store the n elements.
All the stated bounds are valid on a pointer machine.
Additionally, the operation repertoire can be extended to include meld
in O(min{lg m, lg n}) worstcase time,
where m and n are the sizes of the priority queues to be melded.
However, this increases the worstcase running time of decrease to
O(lg lg n).
