Implementing Relaxed Weak Queues
Jens Rasmussen · 2008
Abstract. I have produced a C++ implementation of relaxed weak queues. This newly invented data structure is a simplification of — and supports all priority-queue operations as efficiently as — a run-relaxed heap, namely: get-highest-priority, insert and increase-priority in O(1) worst-case time, and delete in O(lg n) worst-case time, n denoting the number of elements stored prior to the operation. Further, the data structure supports meld in O(min{lgm, lg n}) worst-case time, where m and n denote the sizes of the sub-collections melded. 1.