In computer science, adaptive heap sort is a comparison-based sorting algorithm of the adaptive sort family. It is a variant of heap sort that performs better when the data contains existing order. Published by Christos Levcopoulos and Ola Petersson in 1992, the algorithm utilizes a new measure of presortedness, Osc, as the number of oscillations. Instead of putting all the data into the heap as the traditional heap sort did, adaptive heap sort only takes part of the data into the heap so that the run time will reduce significantly when the presortedness of the data is high.

Heapsort

Heap sort is a sorting algorithm that utilizes binary heap data structure. The method treats an array as a complete binary tree and builds up a Max-Heap/Min-Heap to achieve sorting. It usually involves the following four steps.

1. Build a Max-Heap(Min-Heap): put all the data into the heap so that all nodes are either greater than or equal (less than or equal to for Min-Heap) to each of its child nodes.

2. Swap the first element of the heap with the last element of the heap.

3. Remove the last element from the heap and put it at the end of the list. Adjust the heap so that the first element ends up at the right place in the heap.

4. Repeat Step 2 and 3 until the heap has only one element. Put this last element at the end of the list and output the list. The data in the list will be sorted.

Below is a C/C++ implementation that builds up a Max-Heap and sorts the array after the heap is built.

Measures of presortedness

Measures of presortedness measures the existing order in a given sequence. These measures of presortedness decides the number of data that will be put in to the heap during the sorting process as well as the lower bound of running time.

Oscillations (Osc)

, Cross(xi) is defined as the number edges of the line plot of X that are intersected by a horizontal line through the point (i, xi. The oscillation(Osc.

Other measures

Besides the original Osc measurement, other known measures include the number of inversions Inv, the number of runs Runs, the number of blocks Block, and the measures Max, Exc and Rem. Most of these different measurements are related for adaptive heap sort. Some measures dominate the others: every Osc-optimal algorithm is Inv optimal and Runs optimal; every Inv-optimal algorithm is Max optimal; and every Block-optimal algorithm is Exc optimal and Rem optimal.

Algorithm

Adaptive heap sort is a variant of heap sort that seeks optimality (asymptotically optimal , we put all n elements into the heap and then keep extracting the maximum (or minimum) for n times. Since the time of each max-extraction action is the logarithmic in the size of the heap, the total running time of standard heap sort is \color{Blue} O(n \log n). For adaptive heap sort, instead of putting all the elements into the heap, only the possible maximums of the data (max-candidates) will be put into the heap so that fewer runs are required when each time we try to locate the maximum (or minimum).

First, a Cartesian tree for inputs that are already nearly sorted.

Below is an implementation in pseudo-code:

Input: an array of n elements that need to be sorted

Construct the Cartesian tree l(x)
Insert the root of l(x) into a heap

for i = from 1 to n
{
    Perform ExtractMax on the heap 
    if the max element extracted has any children in l(x)
    {
        retrieve the children in l(x)
        insert the children element into the heap
    }
}

Drawbacks

Despite decades of research, there's still a gap between the theory of adaptive heap sort and its practical use. Because the algorithm makes use of Cartesian trees and pointer manipulation, it has low cache-efficiency and high memory requirements, both of which deteriorate the performance of implementations.

See also

• Adaptive sort

• Heapsort

• Cartesian tree

References