The relaxed min-max heap: A mergeable double-ended priority queue (Q1323336)

A data structure that implements a mergeable double-ended priority queue, namely the relaxed min-max heap, is presented. A relaxed min-max heap of \(n\) items can be constructed in \(O(n)\) time. In the worst case, operations \textit{find-min}( ) and \textit{find-max}( ) can be performed in constant time, while each of the operations \textit{merge}( ), \textit{insert}( ), \textit{delete-min}( ), \textit{decrease-key}( ), and \textit{delete-key}( ) can be performed in \(O(\log n)\) time. Moreover, \textit{insert}( ) has \(O(1)\) amortized running time. If lazy merging is used, \textit{merge}( ) will also have \(O(1)\) worst-case and amortized time. The relaxed min-max heap is the first data structure which achieves these bounds using only two pointers per item.