File Heapsort.h

↰ Parent directory (ADS/sort)

The max-heap on a vector and heapsort (section 10.1.4).

Definition (ADS/sort/Heapsort.h)

Detailed Description

maxHeapRestore( A , i , dim ) moves the item in A[ i ] down, swapping it with its largest child, when the subtrees of the children are max-heaps in A[ 0 .. dim - 1 ]: O( m ) time on a node of height m. heapBuild() calls it from :math:` lfloor n / 2 rfloor - 1 ` down to 0, the places from :math:` lfloor n / 2 rfloor ` on being leaves; since a heap of n items has at most :math:` lceil n / 2^{m+1} rceil ` nodes of height m, its time is :math:`[

Oleft( sum_{m=0}^{lfloor log n rfloor} frac{n}{2^{m+1}} m right) = Oleft( n sum_{m=0}^{infty} frac{m}{2^m} right) = O( n ),

` the series being 2. heapsort() builds the heap and then swaps the maximum A[ 0 ] with the last place of the heap, which shrinks by one, and restores it, in :math:` O( n log n ) ` time and O( 1 ) extra space, since maxHeapRestore() is a loop rather than the recursion of the book (exercise 10.4).

The contracts [see File Contract.h]: maxHeapRestore() and isMaxHeap() need dim <= n, maxHeapRestore() also i < dim, and heapBuild() ends with a heap and heapsort() with the same items sorted, two audits. The functions are defined in Heapsort.tpp.

  1. Montresor, Algoritmi e Strutture Dati, 2025, section 10.1.4, https://algoritmicamente.it/materiali/libro/capitoli/cap10.pdf

      1. Williams, Algorithm 232: Heapsort, Communications of the ACM 7(6), 347-348, 1964, doi:10.1145/512274.512284

    1. Floyd, Algorithm 245: Treesort 3, Communications of the ACM 7(12), 701, 1964, doi:10.1145/355588.365103

Donato Meoli

Dipartimento di Informatica Universita’ di Pisa

by Donato Meoli

Includes

Included By

Namespaces

Functions