The Ultimate Heapsort
Author:Jyrki Katajainen
Published in:Proceedings of the Computing: {T}he 4th Australasian Theory Symposium, Australian Computer Science Communications 20,3, Springer-Verlag Singapore Pte. Ltd. (1998), 87-96
Full text:<ps.gif>PS (264 kB)  
Copyright:© Springer-Verlag

A variant of Heapsort—named Ultimate Heapsort—is presented that sorts n elements in-place in Θ(n log2(n + 1)) worst-case time by performing at most n log2 n + Θ(n) key comparisons and n log2 n + Θ(n) element moves. The secret behind Ultimate Heapsort is that it occasionally transforms the heap it operates with to a two-layer heap which keeps small elements at the leaves. Basically, Ultimate Heapsort is like Bottom-Up Heapsort but, due to the two-layer heap property, an element taken from a leaf has to be moved towards the root only O(1) levels, on an average.

Related:<html.gif>HTML (Technical report)  
  author = {Jyrki Katajainen},
  title = {The Ultimate Heapsort},
  booktitle = {Proceedings of the Computing: {T}he 4th Australasian Theory
  series = {Australian Computer Science Communications},
  volume = {20},
  number = {3},
  publisher = {Springer-Verlag Singapore Pte. Ltd.},
  year = {1998},
  pages = {87--96},
This page was generated by Jyrki Katajainen <> on 04.07.2013.