Bounds for min-max heaps

Very recently a new data structure, called a min-max heap, was presented for implementing the double-ended priority queue. A min-max heap onn keys is constructed inO(n) time; the minimum and maximum keys are found in constant time, and the operations of deleting the minimum, deleting the maximum and inserting a new key into the heap are performed inO(logn) time. In addition, the data structure can be stored implicitly, i.e. in an array ofn elements without using any additional pointers.In this paper, we present lower bound results on the number of comparisons required, in the worst case, for the operations i) to construct a min-max heap on a given set of keys; ii) to convert a min-max heap into a max-min heap; and iii) to merge two min-max heaps into one min-max heap. New upper bounds for the convert and merge operations are also derived. It is found that the main difference between traditional heaps and min-max heaps lies in the time needed to perform the merge operation. While traditional heaps can be merged efficiently, it is shown that min-max heaps are not sublinearly mergeable. Even the seemingly simple task of converting a min-max heap into a max-min heap cannot be performed in less than linear time.This research was supported by the Natural Science and Engineering Council of Canada under Grant No. A0392. (A preliminary version of this paper was presented at the 24th Annual Allerton Conference on Communication, Control and Computing.)