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 priority-queue operations as efficiently as a run-relaxed heap: find-min, insert, and decrease 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. 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}) worst-case time, where m and n are the sizes of the priority queues to be melded. However, this increases the worst-case running time of decrease to O(lg lg n).

@report{EJK2010cR,
  author = {Amr Elmasry and Claus Jensen and Jyrki Katajainen},
  title = {Relaxed weak queues and their implementation on a pointer machine},
  type = {CPH STL Report},
  number = {2010-4},
  institution = {Department of Computer Science, University of Copenhagen},
  year = {2010},
  pagetotal = {18},
}