A Mergeable Double-ended Priority Queue

Abstract

An implementation of a double-ended priority queue is discussed. This data structure referred to as min–max–pair heap can be built in linear time; the operations Delete-min, Delete-max and Insert take O(log n) time, while Find-min and Find-max run in O(1) time. In contrast to the min-max heaps, it is shown that two min–max–pair heaps can be merged in sublinear time. More precisely, two min–max–pair heaps of sizes n and k can be merged in time O(log (n/k) * log k).