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 minimum deletion and deletion, improving the bound of 2 log n + O(1) on the number of element comparisons 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 max{1, log₂ n}. We also give a priority queue that provides, in addition to the above-mentioned methods, the priority-decrease (or decrease-key) method. This priority queue achieves the worst-case cost of O(1) per minimum finding, insertion, and priority decrease; and the worst-case cost of O(log n) with at most log n + O(log log n) element comparisons per minimum deletion and deletion.

@report{EJK2004R,
  author = {Amr Elmasry and Claus Jensen and Jyrki Katajainen},
  title = {A framework for speeding up priority-queue operations},
  type = {CPH STL Report},
  number = {2004-3},
  institution = {Department of Computer Science, University of Copenhagen},
  year = {2004},
  pagetotal = {31},
}