Multipartite Priority Queues

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)$ 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\set{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