Adaptive heap sort
Encyclopedia
The adaptive heap sort is a sorting algorithm
that is similar to heap sort, but uses a randomized binary search tree to structure the input according to any preexisting order. The randomized binary search tree is used to select candidates that are put into the heap, so the heap doesn't need to keep track of all elements. Adaptive heap sort is a part of the adaptive sorting family
.
The first adaptive heapsort was Dijkstra's Smoothsort
.
Sorting algorithm
In computer science, a sorting algorithm is an algorithm that puts elements of a list in a certain order. The most-used orders are numerical order and lexicographical order...
that is similar to heap sort, but uses a randomized binary search tree to structure the input according to any preexisting order. The randomized binary search tree is used to select candidates that are put into the heap, so the heap doesn't need to keep track of all elements. Adaptive heap sort is a part of the adaptive sorting family
Adaptive sort
A sorting algorithm falls into the adaptive sort family if it takes advantage of existing order in its input. It benefits from the presortedness in the input sequence – or a limited amount of disorder for various definitions of measures of disorder – and sorts faster...
.
The first adaptive heapsort was Dijkstra's Smoothsort
Smoothsort
Smoothsort is a comparison-based sorting algorithm. It is a variation of heapsort developed by Edsger Dijkstra in 1981. Like heapsort, smoothsort's upper bound is O...
.