We introduce a data structure which provides efficient heap
operations with respect to the number of element comparisons
performed. Let n denote the size of the heap being manipulated.
Our data structure guarantees the worst-case cost of
O(1) for finding the minimum, inserting an element, extracting an
(unspecified) element, and replacing an element with a smaller
element; and the worst-case cost of O(lg n) with at most lg n +
3 lg lg n + O(1) element comparisons for deleting an element. We
thereby improve the comparison complexity of heap operations known
for run-relaxed heaps and other worst-case efficient heaps.
Furthermore, our data structure supports melding of two heaps of
size m and n at the worst-case cost of O(min{lg m, lg n}).