We introduce a framework for reducing the number of element comparisons performed in priority-queue operations. In particular, we give a priority queue which guarantees the worst-case cost of  O (1) per minimum finding and insertion, and the worst-case cost of  O (log  n ) with at most log  n  +  O (1) element comparisons per deletion, improving the bound of 2 log  n  +  O (1) known for binomial queues. Here,  n  denotes the number of elements stored in the data structure prior to the operation in question, and log  n  equals log 2 (max {2, n}). As an immediate application of the priority queue developed, we obtain a sorting algorithm that is optimally adaptive with respect to the inversion measure of disorder, and that sorts a sequence having  n  elements and  I  inversions with at most  n  log ( I / n ) +  O ( n ) element comparisons.
['Amr Elmasry', 'Claus Jensen', 'Jyrki Katajainen']
Multipartite priority queues