Adaptive heap sort: Difference between revisions

Revision as of 11:43, 27 April 2021

Revision as of 00:52, 14 October 2022

Line 9:

# 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++ implementation that builds up a Max-Heap and sorts the array after the heap is built.<br />

#include <iostream>

<syntaxhighlight lang="c++">

/*

#include <iostream>

''A C++ sample heap sort code that sort an array to an increasing order''

*/*

''A C++ sample heap sort code that sort an array to an increasing order''

using namespace std;

*/

using namespace std;

void heapify(int array[], int start, int end);// A ''function that build up a max-heap binary tree''

void heapify(int array[], int start, int end); // A function that build up a max-heap binary tree

{

void heapify(int parentarray[], =int start;, int end)

{

int child = parent * 2 + 1;

int parent = start;

while (child <= end)

int child = parent * 2 + 1;

{ if (child + 1 <= end ) ''//when there are two child nodes''

while (child <= end)

{

{ if (array[child + 1] ><= end array[child]) // when there are two child nodes

{

if (array[child ++; ''//take1] the bigger> array[child node''])

}{

child ++; //take the bigger child node

}

if (array[parent] > array[child])

{}

if (array[parent] > array[child])
{
return; ''//if the parent node is greater, then it's already heapified''

}

if (array[parent] < array[child]) ''// when child node is greater than parent node''

{

swap (array[parent], array[child]); ''// switch parent and child node''

parent = child;

child = child * 2 + 1; ''//continue the loop, compare the child node and its child nodes''

}

}

}

void heap_sort (int array[], int len); ''// heap_sort function''

void heap_sort (int array[], int len)

{

for (int i = len/2 - 1; i >= 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()

{

int array[] = {42, 1283, 123, 654, 239847, 45, 97, 85, 763, 90, 770, 616, 328, 1444, 911, 315, 38, 5040, 1}; ''//the array that will be sorted''

int array_len = sizeof(array)/sizeof(*array); ''//length of the array''

heap_sort (array, array_len);// heap sort

return 0;

}

</syntaxhighlight>

== Measures of presortedness ==

Line 78 ⟶ 81:

== 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 = <x_1, x_2, x_3, .... ,x_n></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|O(n log n)]].<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><br />

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

Below is an implementation in pseudo-code:<ref name=":0" />

Construct the Cartesian tree ''l''(x)

<syntaxhighlight>

Insert the root of ''l''(x) into a heap

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

for i = from 1 to n

{

Construct the Cartesian tree ''l''(x)

Perform ExtractMax on the heap

ifInsert the maxroot element extracted has any children inof ''l''(x) into a heap

for i = from 1 to n

{

{

retrieve the children in ''l''(x)

insert the children elementPerform intoExtractMax on the heap

if the max element extracted has any children in ''l''(x)

}

{

}<ref name=":0" />

retrieve the children in ''l''(x)

insert the children element into the heap

}

}

</syntaxhighlight>

== Drawbacks ==