tag

#heap-sort

5 pages tagged

Programming › Algorithm Cookbook › Chapter 6. Sorting ›

6.6 Heap Sort

6.6 Heap Sort Heap sort derives order from a heap structure. It first builds a max-heap from the input array, then repeatedly extracts the maximum element and places it at the end of the array. The array itself stores the heap, so the algorithm runs in place. Problem You have an array A[0..n-1] . You want a sorting algorithm with guaranteed $O(n \log n)$ time, constant extra space, and no...
algorithms sorting heap-sort heaps May 4, 2026
Wiki › Algorithms › 01. Searching and Sorting › 6. Elementary Sorting ›

Smoothsort

Smoothsort Smoothsort is an adaptive comparison-based sorting algorithm designed by Edsger Dijkstra. It is related to heapsort, but it uses a forest of Leonardo heaps instead of one binary heap. The main advantage is adaptivity. Smoothsort runs in linear time on already sorted or nearly sorted data, while preserving the same worst-case bound as heapsort. Problem Given a sequence $A$ of length $n$, reorder it such that $$ A[0] \le...
algorithms sorting smoothsort heap-sort adaptive
Wiki › Algorithms › 01. Searching and Sorting › 9. Partial, Online, and Adaptive Sorting ›

Adaptive Heap Sort

Adaptive Heap Sort Adaptive heap sort modifies standard heapsort to take advantage of existing order in the input. While classical heapsort treats all inputs the same, adaptive variants reduce work when the input is already partially sorted. You use it when you want heap-based guarantees with some sensitivity to input structure. Problem Given an array ( A ), sort it while: preserving ( O(n \log n) ) worst-case bounds reducing...
algorithms sorting heap-sort adaptive
Wiki › Algorithms › 01. Searching and Sorting › 6. Elementary Sorting ›

Weak Heap Sort

Weak Heap Sort Weak heap sort is a comparison-based sorting algorithm that improves upon heapsort by reducing the number of comparisons. It uses a structure called a weak heap, where the tree shape is similar to a binary heap but ordering constraints are relaxed and encoded using a bit array. The algorithm maintains a single root heap and repeatedly extracts the maximum element. Problem Given a sequence $A$ of length...
algorithms sorting weak-heap heap-sort
Wiki › Algorithms › 01. Searching and Sorting › 9. Partial, Online, and Adaptive Sorting ›

Smoothsort Adaptive Heap Sort

Smoothsort Adaptive Heap Sort Smoothsort is an adaptive heap-based sorting algorithm. It preserves the in-place and worst-case guarantees of heapsort, but it performs much less work when the input is already close to sorted. You use it when constant extra space matters and the input may contain existing order. Problem Given an array ( A ) of length ( n ), sort it in place while taking advantage of nearly...
algorithms sorting smoothsort heap-sort adaptive