adaptive heap sort

comparison-based sorting algorithm

Uses your system voice; voice and rate in settings.

Q4680746Snapshot

≈ 4 min read

Names in other languages

  • taதகவமைப்பு குவியல் வகை வரிசையாக்கம்
  • Српскиprilagodljivo hip sortiranje
  • Portuguêsheap sort adaptativo
  • Englishadaptive heap sort

Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.

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 19921, 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. /* A C/C++ sample heap sort code that sort an array to an increasing order / // A function that build up a max-heap binary tree void heapify(int array[], int start, int end) { int parent = start; int child = parent * 2 + 1; while (child array[child]) { child ++; //take the bigger child node } } if (array[parent] > array[child]) { return; //if the parent node is greater, then it's already heapified } if (array[parent] = 0; i--) //Step 1: build up the max-heap { heapify(array, i, len); } for (int i = len - 1; i >= 0; i--) //Step 4: repeat step 2 and 3 till finished { swap(array[0], array[i]); // Step 2: put the max at the end of the array heapify (array, 0, i-1); // Step 3: remove the max from the tree and heapify again } } int main() { //the array that will be sorted int array[] = {42, 1283, 123, 654, 239847, 45, 97, 85, 763, 90, 770, 616, 328, 1444, 911, 315, 38, 5040, 1}; int array_len = sizeof(array)/sizeof(*array); //length of the array heap_sort (array, array_len); return 0; } For sequence X = \langle x_1, x_2, x_3, \dots ,x_n \rangle , Cross(x i ) is defined as the number edges of the line plot of X that are intersected by a horizontal line through the point (i, x i ). Mathematically, it is defined as \mathit{Cross}(x_i) = \{j \mid \min\{ x_j, x_{j+1}\} . The oscillation(Osc) of X is just the total number of intersections, defined as \mathit{Osc}(x) = \textstyle \sum_{i=1}^n \displaystyle\lVert \mathit{Cross}(x_i) \rVert .

Adaptive heap sort is a variant of heap sort that seeks optimality (asymptotically optimal) with respect to the lower bound derived with the measure of presortedness by taking advantage of the existing order in the data. In heap sort, for a data X = \langle x_1, x_2, x_3, \dots ,x_n \rangle , 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 is built from the input in O(n) time by putting the data into a binary tree and making each node in the tree is greater(or smaller) than all its children nodes, and the root of the Cartesian tree is inserted into an empty binary heap.

Then repeatedly extract the maximum from the binary heap, retrieve the maximum in the Cartesian tree, and add its left and right children (if any) which are themselves Cartesian trees, to the binary heap. If the input is already nearly sorted, the Cartesian trees will be very unbalanced, with few nodes having left and right children, resulting in the binary heap remaining small, and allowing the algorithm to sort more quickly than O(n\log n) 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 } }

See also

Adaptive sort Heapsort Cartesian tree

Text derived from https://en.wikipedia.org/w/index.php?oldid=1318332272 under CC BY-SA 4.0; modifications have been made.

References

  1. ↩Wikipedia “adaptive heap sort” revision 1318332272 · retrieved 2026-10-20 publication date (×1) · confidence 0.95 revision URL

Provenance

snapshot adaptive-heap-sort-535092-1bba040ef7ddabb9 · hash 1bba040ef7ddabb93933d5e439c17e7136ee63ff89687f42bcc1b2bc16a11641 · captured 1761198473.0 · version history

Cite this page as: encyclopegia.org, “adaptive heap sort”, snapshot adaptive-heap-sort-535092-1bba040ef7ddabb9. https://encyclopegia.org/a/adaptive-heap-sort