Container whose elements have two different orders: by priority and by lookup key.
Supports efficient implementation of the following operations:
- insertion (O(log n)),
- lookup by key (O(log n)),
- deletion by key (O(log n)),
- access to minimal-by-priority element (O(1)),
- deletion of minimal-by-priority element (O(log n)).
Implemented using FingerTree.
- Type Params
- A
element type
- K
lookup key. Unique—the queue holds at most one element with any given key.
- P
priority of an element. Multiple elements can have the same priority.
- Companion
- object
Value members
Concrete methods
Removes elements with priority less than p.
Removes elements with priority less than p.
''O(min(k*log(n), (n-k)*log(n), n))'', where ''k'' is the number of actually removed elements. For large ''k'', this method is more efficient than iterated deleteMin.
To also return the removed elements, use splitBeforePrio.
Removes elements with priority less than or equal to p.
Removes elements with priority less than or equal to p.
''O(min(k*log(n), (n-k)*log(n), n))'', where ''k'' is the number of actually removed elements. For large ''k'', this method is more efficient than iterated deleteMin.
To also return the removed elements, use splitAfterPrio.
Removes an element with minimum priority.
Removes an element with minimum priority.
If there are multiple elements with the same minimum priority, it is guaranteed to remove the one returned by minimum.
''O(log(n))''.
If this queue is empty, returns this.
Inserts the given element into this queue.
Inserts the given element into this queue.
If an element with the same key is already present in this queue, it is replaced by elem
and the replaced element is returned in the second part of the returned pair.
Returns an element with minimum priority, or Maybe.Empty if this queue is empty.
Returns an element with minimum priority, or Maybe.Empty if this queue is empty.
If there are multiple elements with the same minimum priority, it is unspecified which of them is returned.
Removes an element by key.
Removes an element by key.
Returns the removed element, if any, in the second part of the returned pair.
Splits this queue into elements with priority less than or equal to p
and elements with priority greater than p.
Splits this queue into elements with priority less than or equal to p
and elements with priority greater than p.
Splits this queue into elements with priority less than p
and elements with priority greater than or equal to p.
Splits this queue into elements with priority less than p
and elements with priority greater than or equal to p.