We consider the classical problem of representing a collection of
priority queues under the operations find-min, insert,
decrease, meld, delete, and delete-min. In the
comparison-based model, if the first four operations are to be
supported in constant time, the last two operations must
take at least logarithmic time. Brodal showed that his
worst-case efficient priority queues achieve these worst-case bounds.
Unfortunately, this data structure is involved and the time bounds hide large
constants. We describe a new variant of the worst-case efficient priority
queues that relies on extended regular counters and provides the same
asymptotic time and space bounds as the original. Due to the conceptual
separation of the operations on regular counters and all other operations,
our data structure is simpler and easier to describe and understand.
Also, the constants in the time and space bounds are smaller.
In addition, we give an implementation of our structure on a pointer machine.
For our pointer-machine implementation, decrease and meld are asymptotically
slower and require O(lglg n) worst-case time, where n denotes the number
of elements stored in the resulting priority queue.