The reader may have noticed that the performance of the external heapsort is mostly due to the fact that only one heap operation is executed for every S elements to be sorted. The situation where a heap is to be used as a priority queue is different in that the heap must be able to handle single element requests efficiently. The simple way to achieve this, is by providing an insertion buffer organized as a traditional heap, and an extraction buffer which is kept sorted internally. Each buffer is the size of a single page. These buffers bundles the requests, so that there is executed at most one heap operation for every S requests.
The idea is that the maximum element of the heap is either in the insert buffer or the extract buffer. Only if both buffers are empty, is it in the external heap.
The buffer management is fairly straightforward - Empty the insert buffer when it is full.- Fill the extract buffer when it is empty. - so I will not go into details here.
An implementation along these lines is provided in heaplab directory extpq/.