The Weak-Heap Data Structure: Variants and Applications1

The weak heap is a priority queue that was introduced as a competitive structure for sorting. Its array-based form supports the operations find-min in O(1) worst-case time, and insert and delete-min in O(lg n) worst-case time using at most dlg ne element comparisons. Additionally, its pointer-based form supports delete and decrease in O(lg n) worst-case time using at most dlg ne element comparisons. In this paper we enhance this data structure as follows: 1. We improve the array-based form to support insert in O(1) amortized time. The main idea is to temporarily store the inserted elements in a buffer, and, once the buffer is full, to move its elements to the heap using an efficient bulk-insertion procedure. As an application, we use this variant in the implementation of adaptive heapsort. Accordingly, we guarantee, for several measures of disorder, that the formula expressing the number of element comparisons performed by the algorithm is optimal up to the constant factor of the high-order term. Unlike other previous constant