Adaptive heap sort: Difference between revisions

Revision as of 01:22, 17 October 2022

Revision as of 05:58, 17 October 2022

Line 76:

=== Oscillations (''Osc'') ===

For sequence <math>X = <\langle x_1, x_2, x_3, .... ,x_n> \rangle</math>, ''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 <math>\mathit{Cross}(x_i) = \{j \mid \min\{ x_j, x_{j+1}\} < x_i < \max\{ x_j, x_{j+1}\} \text{ for } 1 \leq j < n \}\text{, for }1\leq i \leq n</math>. The oscillation(''Osc'') of X is just the total number of intersections, defined as <math>\mathit{Osc}(x) = \textstyle \sum_{i=1}^n \displaystyle\lVert Cross(x_i) \rVert</math>.<ref name=":0" />

=== Other measures ===

Line 83:

== Algorithm ==

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 <math>X = <\langle x_1, x_2, x_3, .... ,x_n> \rangle</math> , 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 [[Big O notation|<math>\color{Blue} O(n \log n)</math>]].<ref name=":1" /> 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 <math>O(n)</math> 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 <math>O(n\log n)</math> for inputs that are already nearly sorted.<ref>{{Cite web|url=http://www.keithschwarz.com/interesting/code/?dir=cartesian-tree-sort|title=Archive of Interesting Code|website=www.keithschwarz.com|access-date=2019-10-31}}</ref>