{"history":[],"article":{"id":"1323f8b9-eaa6-4115-8255-01c9d9c88e0f","title":"Heapsort","slug":"heapsort","content":":::summary\n**Class:** [Sorting algorithm](https://bliptext.com/articles/sorting-algorithm) \n**Data:** [Array](https://bliptext.com/articles/array-data-structure) \n**Time:** O(n\\log n) \n**Average -time:** O(n\\log n) \n**Best -time:** O(n\\log n) (distinct keys) · or O(n) (equal keys) \n**Space:** O(n) total O(1) auxiliary \n:::\n\n# \nIn [computer science](https://bliptext.com/articles/computer-science), **heapsort** is a [comparison-based](https://bliptext.com/articles/comparison-sort) [sorting algorithm](https://bliptext.com/articles/sorting-algorithm) which can be thought of as \"an implementation of [selection sort](https://bliptext.com/articles/selection-sort) using the right [data structure](https://bliptext.com/articles/data-structure).\"\nLike selection sort, heapsort divides its input into a sorted and an unsorted region, and it iteratively shrinks the unsorted region by extracting the largest element from it and inserting it into the sorted region.\nUnlike selection sort, heapsort does not waste time with a linear-time scan of the unsorted region; rather, heap sort maintains the unsorted region in a [heap data structure](https://bliptext.com/articles/heap-data-structure) to efficiently find the largest element in each step.\nAlthough somewhat slower in practice on most machines than a well-implemented [quicksort](https://bliptext.com/articles/quicksort), it has the advantages of very simple implementation and a more favorable worst-case\nO(n log n)\nruntime.\nMost real-world quicksort variants include an implementation of heapsort as a fallback should they detect that quicksort is becoming degenerate.\nHeapsort is an [in-place algorithm](https://bliptext.com/articles/in-place-algorithm), but it is not a [stable sort](https://bliptext.com/articles/stable-sort).\nHeapsort was invented by [J. W. J. Williams](https://bliptext.com/articles/j-w-j-williams) in 1964.\nThe paper also introduced the [binary heap](https://bliptext.com/articles/binary-heap) as a useful data structure in its own right.\nIn the same year, [Robert W. Floyd](https://bliptext.com/articles/robert-w-floyd) published an improved version that could sort an array in-place, continuing his earlier research into the [treesort](https://bliptext.com/articles/treesort) algorithm.\n\n# Overview\nThe heapsort algorithm can be divided into two phases: heap construction, and heap extraction.\nThe heap is an [implicit data structure](https://bliptext.com/articles/implicit-data-structure) which takes no space beyond the array of objects to be sorted; the array is interpreted as a [complete binary tree](https://bliptext.com/articles/complete-binary-tree) where each array element is a node and each node's parent and child links are defined by simple arithmetic on the array indexes.\nFor a zero-based array, the root node is stored at index 0, and the nodes linked to node i are\niLeftChild(i) = 2⋅i + 1\niRightChild(i) = 2⋅i + 2\niParent(i) = floor((i−1) / 2)\nwhere the [floor function](https://bliptext.com/articles/floor-function) rounds down to the preceding integer.\nFor a more detailed explanation, see.\nThis binary tree is a max-heap when each node is greater than or equal to both of its children.\nEquivalently, each node is less than or equal to its parent.\nThis rule, applied throughout the tree, results in the maximum node being located at the root of the tree.\nIn the first phase, a heap is built out of the data (see ).\nIn the second phase, the heap is converted to a sorted array by repeatedly removing the largest element from the heap (the root of the heap), and placing it at the end of the array.\nThe heap is updated after each removal to maintain the heap property.\nOnce all objects have been removed from the heap, the result is a sorted array.\nHeapsort is normally performed in place.\nDuring the first phase, the array is divided into an unsorted prefix and a heap-ordered suffix (initially empty).\nEach step shrinks the prefix and expands the suffix.\nWhen the prefix is empty, this phase is complete.\nDuring the second phase, the array is divided into a heap-ordered prefix and a sorted suffix (initially empty).\nEach step shrinks the prefix and expands the suffix.\nWhen the prefix is empty, the array is sorted.\n\n# Algorithm\nThe heapsort algorithm begins by rearranging the array into a binary max-heap.\nThe algorithm then repeatedly swaps the root of the heap (the greatest element remaining in the heap) with its last element, which is then declared to be part of the sorted suffix.\nThen the heap, which was damaged by replacing the root, is repaired so that the greatest element is again at the root.\nThis repeats until only one value remains in the heap.\nThe steps are:\nO(n)\noperations.\nThe heapify operation is run once, and is\nO(n)\nin performance.\nThe siftDown function is called n times and requires\nO(log n)\nwork each time, due to its traversal starting from the root node.\nTherefore, the performance of this algorithm is\nO(n + n log n) = O(n log n)\n.\nThe heart of the algorithm is the siftDown function.\nThis constructs binary heaps out of smaller heaps, and may be thought of in two equivalent ways:\nTo establish the max-heap property at the root, up to three nodes must be compared (the root and its two children), and the greatest must be made the root.\nThis is most easily done by finding the greatest child, then comparing that child to the root.\nThere are three cases:\nThe number of iterations in any one siftdown call is bounded by the height of the tree, which is\n⌊log2 n⌋ = O(log n)\n.\n\n## Pseudocode\nThe following is a simple way to implement the algorithm in [pseudocode](https://bliptext.com/articles/pseudocode).\nArrays are [zero-based](https://bliptext.com/articles/comparison-of-programming-languages-array) and swap is used to exchange two elements of the array.\nMovement 'down' means from the root towards the leaves, or from lower indices to higher.\nNote that during the sort, the largest element is at the root of the heap at a[0], while at the end of the sort, the largest element is in a[end].\n**procedure** heapsort(a, count) **is**\n**input:** an unordered array a of length count\n(Build the heap in array a so that largest value is at the root)\nheapify(a, count)\n(The following loop maintains the [invariants](https://bliptext.com/articles/loop-invariant) that a[0:end−1] is a heap, and every element a[end:count−1] beyond end is greater than everything before it, i.e. a[end:count−1] is in sorted order.)\nend ← count\n**while** end > 1 **do**\n(the heap size is reduced by one)\nend ← end − 1\n(a[0] is the root and largest value. The swap moves it in front of the sorted elements.)\nswap(a[end], a[0])\n(the swap ruined the heap property, so restore it)\nsiftDown(a, 0, end)\nThe sorting routine uses two subroutines, heapify and siftDown.\nThe former is the common in-place heap construction routine, while the latter is a common subroutine for implementing heapify.\n(Put elements of 'a' in heap order, in-place)\n**procedure** heapify(a, count) **is**\n(start is initialized to the first leaf node)\n(the last element in a 0-based array is at index count-1; find the parent of that element)\nstart ← iParent(count-1) + 1\n**while** start > 0 **do**\n(go to the last non-heap node)\nstart ← start − 1\n(sift down the node at index 'start' to the proper place such that all nodes below the start index are in heap order)\nsiftDown(a, start, count)\n(after sifting down the root all nodes/elements are in heap order)\n(Repair the heap whose root element is at index 'start', assuming the heaps rooted at its children are valid)\n**procedure** siftDown(a, root, end) **is**\n**while** iLeftChild(root) < end **do** (While the root has at least one child)\nchild ← iLeftChild(root) (Left child of root)\n(If there is a right child and that child is greater)\n**if** child+1 < end **and** a[child] < a[child+1] **then**\nchild ← child + 1\n**if** a[root] < a[child] **then**\nswap(a[root], a[child])\nroot ← child (repeat to continue sifting down the child now)\n**else**\n(The root holds the largest element. Since we may assume the heaps rooted at the children are valid, this means that we are done.)\n**return**\nThe heapify procedure operates by building small heaps and repeatedly merging them using siftDown.\nIt starts with the leaves, observing that the they are trivial but valid heaps by themselves, and then adds parents.\nStarting with element\nn/2\nand working backwards, each internal node is made the root of a valid heap by sifting down.\nThe last step is sifting down the first element, after which the entire array obeys the heap property.\nTo see that this takes\nO(n)\ntime, count the worst-case number of siftDown iterations.\nThe last half of the array requires zero iterations, the preceding quarter requires at most one iteration, the eighth before that requires at most two iterations, the sixteenth before that requires at most three, and so on.\nLooked at a different way, if we assume every siftDown call requires the maximum number of iterations, the first half of the array requires one iteration, the first quarter requires one more (total 2), the first eighth requires yet another (total 3), and so on.\nThis totals\nn/2 + n/4 + n/8 + ⋯ = n⋅(1/2 + 1/4 + 1/8 + ⋯)\n, where the infinite sum is a well-known [geometric series](https://bliptext.com/articles/geometric-series) whose sum is\n1\n, thus the product is simply n.\nThe above is an approximation.\nThe exact worst-case number of comparisons during the heap-construction phase of heapsort is known to be equal to\n2n − 2s2(n) − e2(n)\n, where\ns2(n)\nis the [number of 1 bits](https://bliptext.com/articles/hamming-weight) in the binary representation of n and\ne2(n)\nis the [number of trailing 0 bits](https://bliptext.com/articles/find-first-set).\n\n## Standard implementation\nAlthough it is convenient to think of the two phases separately, most implementations combine the two, allowing a single instance of siftDownto be [expanded inline](https://bliptext.com/articles/inline-expansion).\nTwo variables (here, start and end) keep track of the bounds of the heap area.\nThe portion of the array before start is unsorted, while the portion beginning at end is sorted.\nHeap construction decreases start until it is zero, after which heap extraction decreases end until it is 1 and the array is entirely sorted.\n**procedure** heapsort(a, count) **is**\n**input:** an unordered array a of length count\nstart ← floor(count/2)\nend ← count\n**while** end > 1 **do**\n**if** start > 0 **then** (Heap construction)\nstart ← start − 1\n**else** (Heap extraction)\nend ← end − 1\nswap(a[end], a[0])\n(The following is siftDown(a, start, end))\nroot ← start\n**while** iLeftChild(root) < end **do**\nchild ← iLeftChild(root)\n(If there is a right child and that child is greater)\n**if** child+1 < end **and** a[child] < a[child+1] **then**\nchild ← child + 1\n**if** a[root] < a[child] **then**\nswap(a[root], a[child])\nroot ← child (repeat to continue sifting down the child now)\n**else**\n**break** (return to outer loop)\n\n# Variations\n\n## Williams' heap construction\nThe description above uses Floyd's improved heap-construction algorithm, which operates in\nO(n)\ntime and uses the same siftDown primitive as the heap-extraction phase.\nAlthough this algorithm, being both faster and simpler to program, is used by all practical heapsort implementations, Williams' original algorithm may be easier to understand, and is needed to implement a more general binary heap [priority queue](https://bliptext.com/articles/priority-queue).\nRather than merging many small heaps, Williams' algorithm maintains one single heap at the front of the array and repeatedly appends an additional element using a siftUp primitive.\nBeing at the end of the array, the new element is a leaf and has no children to worry about, but may violate the heap property by being greater than its parent.\nIn this case, exchange it with its parent and repeat the test until the parent is greater or there is no parent (we have reached the root).\nIn pseudocode, this is:\n**procedure** siftUp(a, end) **is**\n**input:** a is the array, which heap-ordered up to end-1.\nend is the node to sift up.\n**while** end > 0\nparent := iParent(end)\n**if** a[parent] < a[end] **then** (out of max-heap order)\nswap(a[parent], a[end])\nend := parent (continue sifting up)\n**else**\n**return**\n**procedure** heapify(a, count) **is**\n(start with a trivial single-element heap)\nend := 1\n**while** end < count\n(sift up the node at index end to the proper place such that all nodes above the end index are in heap order)\nsiftUp(a, end)\nend := end + 1\n(after sifting up the last node all nodes are in heap order)\nTo understand why this algorithm can take asymptotically more time to build a heap (\nO(n log n)\nvs.\nO(n)\nworst case), note that in Floyd's algorithm, almost all the calls to siftDown operations apply to very small heaps. Half the heaps are height-1 trivial heaps and can be skipped entirely, half of the remainder are height-2, and so on. Only two calls are on heaps of size\nn/2\n, and only one siftDown operation is done on the full n-element heap.\nThe overall average siftDown operation takes\nO(1)\ntime.\nIn contrast, Williams' algorithm most of the calls to siftUp are made on large heaps of height\nO(log n)\n. Half of the calls are made with a heap size of\nn/2\nor more, three-quarters are made with a heap size of\nn/4\nor more, and so on.\nAlthough the average number of steps is similar to Floyd's technique, pre-sorted input will cause the worst case: each added node is sifted up to the root, so the average call to siftUp will require approximately\n(log2n − 1)/2 + (log2n − 2)/4 + (log2n − 3)/8 + ⋯\n= log2n − (1 + 1/2 + 1/4 + ⋯)\n= log2n − 2\niterations.\nBecause it is dominated by the second heap-extraction phase, the heapsort algorithm itself has\nO(n log n)\ntime complexity using either version of heapify.\n# [Difference in time complexity between the \"siftDown\" version and the \"siftUp\" version. | upload.wikimedia.org/wikipedia/commons/a/ac/Binary///heap///bottomup///vs///topdown.svg]\n\n## Bottom-up heapsort\nBottom-up heapsort is a variant which reduces the number of comparisons required by a significant factor.\nWhile ordinary \"top-down\" heapsort requires\n2n log2 n + O(n)\ncomparisons worst-case and on average, the bottom-up variant requires\nn log2n + O(1)\ncomparisons on average, and\n1.5n log2n + O(n)\nin the worst case.\nIf comparisons are cheap (e.g. integer keys) then the difference is unimportant, as top-down heapsort compares values that have already been loaded from memory.\nIf, however, comparisons require a [function call](https://bliptext.com/articles/function-call) or other complex logic, then bottom-up heapsort is advantageous.\nThis is accomplished by using a more elaborate siftDown procedure.\nThe change improves the linear-time heap-building phase slightly, but is more significant in the second phase.\nLike top-down heapsort, each iteration of the second phase extracts the top of the heap, a[0], and fills the gap it leaves with a[end], then sifts this latter element down the heap.\nBut this element came from the lowest level of the heap, meaning it is one of the smallest elements in the heap, so the sift-down will likely take many steps to move it back down.\nIn top-down heapsort, each step of siftDown requires two comparisons, to find the minimum of three elements: the new node and its two children.\nBottom-up heapsort conceptually replaces the root with a value of −∞ and sifts it down using only one comparison per level (since no child can possibly be less than −∞) until the leaves are reached, then replaces the −∞ with the correct value and sifts it up (again, using one comparison per level) until the correct position is found.\nThis places the root in the same location as top-down siftDown, but fewer comparisons are required to find that location.\nFor any single siftDown operation, the bottom-up technique is advantageous if the number of downward movements is at least 2/3 of the height of the tree (when the number of comparisons is 4/3 times the height for both techniques), and it turns out that this is more than true on average, even for worst-case inputs.\nA naïve implementation of this conceptual algorithm would cause some redundant data copying, as the sift-up portion undoes part of the sifting down.\nA practical implementation searches downward for a leaf where −∞ would be placed, then upward for where the root should be placed.\nFinally, the upward traversal continues to the root's starting position, performing no more comparisons but exchanging nodes to complete the necessary rearrangement.\nThis optimized form performs the same number of exchanges as top-down siftDown.\nBecause it goes all the way to the bottom and then comes back up, it is called **heapsort with bounce** by some authors.\n**function** leafSearch(a, i, end) **is**\nj ← i **while** iRightChild(j) < end **do**\n(Determine which of j's two children is the greater)\n**if** a[iRightChild(j)] > a[iLeftChild(j)] **then**\nj ← iRightChild(j)\n**else**\nj ← iLeftChild(j)\n(At the last level, there might be only one child)\n**if** iLeftChild(j) < end **then**\nj ← iLeftChild(j)\n**return** j\nThe return value of the is used in the modified routine:\n**procedure** siftDown(a, i, end) **is**\nj ← leafSearch(a, i, end)\n**while** a[i] > a[j] **do**\nj ← iParent(j)\n**while** j > i **do**\nswap(a[i], a[j])\nj ← iParent(j)\nBottom-up heapsort was announced as beating quicksort (with median-of-three pivot selection) on arrays of size ≥16000.\nA 2008 re-evaluation of this algorithm showed it to be no faster than top-down heapsort for integer keys, presumably because modern [branch prediction](https://bliptext.com/articles/branch-prediction) nullifies the cost of the predictable comparisons which bottom-up heapsort manages to avoid.\nA further refinement does a [binary search](https://bliptext.com/articles/binary-search) in the upward search, and sorts in a worst case of\n(n+1)(log2(n+1) + log2 log2(n+1) + 1.82) + O(log2n)\ncomparisons, approaching [the information-theoretic lower bound](https://bliptext.com/articles/comparison-sort) of\nn log2n − 1.4427n\ncomparisons.\nA variant which uses two extra bits per internal node (n−1 bits total for an n-element heap) to cache information about which child is greater (two bits are required to store three cases: left, right, and unknown) uses less than\nn log2n + 1.1n\ncompares.\n\n## Other variations\nn log2n + O(n)\ncomparisons.\nWhen the maximum is taken, rather than fill the vacated space with an unsorted data value, fill it with a\n−∞\nsentinel value, which never \"bounces\" back up.\nIt turns out that this can be used as a primitive in an in-place (and non-recursive) \"QuickHeapsort\" algorithm.\nFirst, you perform a quicksort-like partitioning pass, but reversing the order of the partitioned data in the array.\nSuppose ([without loss of generality](https://bliptext.com/articles/without-loss-of-generality)) that the smaller partition is the one greater than the pivot, which should go at the end of the array, but our reversed partitioning step places it at the beginning.\nForm a heap out of the smaller partition and do out-of-place heapsort on it, exchanging the extracted maxima with values from the end of the array.\nThese are less than the pivot, meaning less than any value in the heap, so serve as\n−∞\nsentinel values.\nOnce the heapsort is complete (and the pivot moved to just before the now-sorted end of the array), the order of the partitions has been reversed, and the larger partition at the beginning of the array may be sorted in the same way.\n(Because there is no non-[tail recursion](https://bliptext.com/articles/tail-recursion), this also eliminates quicksort's\nO(log n)\nstack usage.)\nO(n log n)\n. The advantage of smoothsort is that it comes closer to\nO(n)\ntime if the [input is already sorted to some degree](https://bliptext.com/articles/adaptive-sort), whereas heapsort averages\nO(n log n)\nregardless of the initial sorted state.\nDue to its complexity, smoothsort is rarely used.\nO(n)\ntime, and its root is placed in a 1-element binary heap.\nThen we repeatedly extract the minimum from the binary heap, output the tree's root element, and add its left and right children (if any) which are themselves Cartesian trees, to the binary heap.\nAs they show, 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\nO(n log n)\nfor inputs that are already nearly sorted.\nn log2 n+O(1)\ncomparisons in the worst case, close to the theoretical minimum, using one extra bit of state per node.\nWhile this extra bit makes the algorithms not truly in-place, if space for it can be found inside the element, these algorithms are simple and efficient, but still slower than binary heaps if key comparisons are cheap enough (e.g. integer keys) that a constant factor does not matter.\nn log2 n+O(1)\ncomparisons, and a similar number of element moves.\nIt is, however, even more complex and not justified unless comparisons are very expensive.\n\n# Comparison with other sorts\nHeapsort primarily competes with [quicksort](https://bliptext.com/articles/quicksort), another very efficient general purpose in-place unstable comparison-based sort algorithm.\nHeapsort's primary advantages are its simple, non-[recursive](https://bliptext.com/articles/recursion-computer-science) code, minimal auxiliary storage requirement, and reliably good performance: its best and worst cases are within a small constant factor of each other, and of the [theoretical lower bound on comparison sorts](https://bliptext.com/articles/comparison-sort).\nWhile it cannot do better than\nO(n log n)\nfor pre-sorted inputs, it does not suffer from quicksort's\nO(n2)\nworst case, either.\nReal-world quicksort implementations use a variety of [heuristics](https://bliptext.com/articles/heuristic) to avoid the worst case, but that makes their implementation far more complex, and implementations such as [introsort](https://bliptext.com/articles/introsort) and pattern-defeating quicksort use heapsort as a last-resort fallback if they detect degenerate behaviour.\nThus, their worst-case performance is slightly worse than if heapsort had been used from the beginning.\nHeapsort's primary disadvantages are its poor [locality of reference](https://bliptext.com/articles/locality-of-reference) and its inherently serial nature; the accesses to the implicit tree are widely scattered and mostly random, and there is no straightforward way to convert it to a [parallel algorithm](https://bliptext.com/articles/parallel-algorithm).\nThe worst-case performance guarantees make heapsort popular in [real-time computing](https://bliptext.com/articles/real-time-computing), and systems concerned with maliciously chosen inputs such as the Linux kernel.\nThe combination of small implementation and dependably [\"good enough\"](https://bliptext.com/articles/principle-of-good-enough) performance make it popular in [embedded systems](https://bliptext.com/articles/embedded-system), and generally any application where sorting is not a [performance bottleneck](https://bliptext.com/articles/bottleneck-software).\nE.g. heapsort is ideal for sorting a list of [filenames](https://bliptext.com/articles/filename) for display, but a [database management system](https://bliptext.com/articles/database-management-system) would probably want a more aggressively optimized sorting algorithm.\nA well-implemented quicksort is usually 2–3 times faster than heapsort.\nAlthough quicksort requires fewer comparisons, this is a minor factor.\n(Results claiming twice as many comparisons are measuring the top-down version; see .) The main advantage of quicksort is its much better locality of reference: partitioning is a linear scan with good spatial locality, and the recursive subdivision has good temporal locality.\nWith additional effort, quicksort can also be implemented in mostly [branch-free code](https://bliptext.com/articles/branch-free-code), and multiple CPUs can be used to sort subpartitions in parallel.\nThus, quicksort is preferred when the additional performance justifies the implementation effort.\nThe other major\nO(n log n)\nsorting algorithm is [merge sort](https://bliptext.com/articles/merge-sort), but that rarely competes directly with heapsort because it is not in-place.\nMerge sort's requirement for\nΩ(n)\nextra space (roughly half the size of the input) is usually prohibitive except in the situations where merge sort has a clear advantage:\n\n# Example\nThe examples sort the values { 6, 5, 3, 1, 8, 7, 2, 4 } in increasing order using both heap-construction algorithms.\nThe elements being compared are shown in a **bold** font.\nThere are typically two when sifting up, and three when sifting down, although there may be fewer when the top or bottom of the tree is reached.\n\n## Heap construction (Williams' algorithm)\n\n## Heap construction (Floyd's algorithm)\n\n## Heap extraction","current_revision":null,"created_by":"kACnuQmH5k9Nr5VNVEpVeg7XpvUmMctD","created_at":"2025-01-25T17:21:03.177Z","updated_at":"2025-01-25T17:21:03.177Z","search_vector":"'heapsort':1","search_content":" \n**Class:** [Sorting algorithm](https://bliptext.com/articles/sorting-algorithm) \n**Data:** [Array](https://bliptext.com/articles/array-data-structure) \n**Time:** O(n\\log n) \n**Average -time:** O(n\\log n) \n**Best -time:** O(n\\log n) (distinct keys) · or O(n) (equal keys) \n**Space:** O(n) total O(1) auxiliary \n \n\n# \nIn [computer science](https://bliptext.com/articles/computer-science), **heapsort** is a [comparison-based](https://bliptext.com/articles/comparison-sort) [sorting algorithm](https://bliptext.com/articles/sorting-algorithm) which can be thought of as \"an implementation of [selection sort](https://bliptext.com/articles/selection-sort) using the right [data structure](https://bliptext.com/articles/data-structure).\"\nLike selection sort, heapsort divides its input into a sorted and an unsorted region, and it iteratively shrinks the unsorted region by extracting the largest element from it and inserting it into the sorted region.\nUnlike selection sort, heapsort does not waste time with a linear-time scan of the unsorted region; rather, heap sort maintains the unsorted region in a [heap data structure](https://bliptext.com/articles/heap-data-structure) to efficiently find the largest element in each step.\nAlthough somewhat slower in practice on most machines than a well-implemented [quicksort](https://bliptext.com/articles/quicksort), it has the advantages of very simple implementation and a more favorable worst-case\nO(n log n)\nruntime.\nMost real-world quicksort variants include an implementation of heapsort as a fallback should they detect that quicksort is becoming degenerate.\nHeapsort is an [in-place algorithm](https://bliptext.com/articles/in-place-algorithm), but it is not a [stable sort](https://bliptext.com/articles/stable-sort).\nHeapsort was invented by [J. W. J. Williams](https://bliptext.com/articles/j-w-j-williams) in 1964.\nThe paper also introduced the [binary heap](https://bliptext.com/articles/binary-heap) as a useful data structure in its own right.\nIn the same year, [Robert W. Floyd](https://bliptext.com/articles/robert-w-floyd) published an improved version that could sort an array in-place, continuing his earlier research into the [treesort](https://bliptext.com/articles/treesort) algorithm.\n\n# Overview\nThe heapsort algorithm can be divided into two phases: heap construction, and heap extraction.\nThe heap is an [implicit data structure](https://bliptext.com/articles/implicit-data-structure) which takes no space beyond the array of objects to be sorted; the array is interpreted as a [complete binary tree](https://bliptext.com/articles/complete-binary-tree) where each array element is a node and each node's parent and child links are defined by simple arithmetic on the array indexes.\nFor a zero-based array, the root node is stored at index 0, and the nodes linked to node i are\niLeftChild(i) = 2⋅i + 1\niRightChild(i) = 2⋅i + 2\niParent(i) = floor((i−1) / 2)\nwhere the [floor function](https://bliptext.com/articles/floor-function) rounds down to the preceding integer.\nFor a more detailed explanation, see.\nThis binary tree is a max-heap when each node is greater than or equal to both of its children.\nEquivalently, each node is less than or equal to its parent.\nThis rule, applied throughout the tree, results in the maximum node being located at the root of the tree.\nIn the first phase, a heap is built out of the data (see ).\nIn the second phase, the heap is converted to a sorted array by repeatedly removing the largest element from the heap (the root of the heap), and placing it at the end of the array.\nThe heap is updated after each removal to maintain the heap property.\nOnce all objects have been removed from the heap, the result is a sorted array.\nHeapsort is normally performed in place.\nDuring the first phase, the array is divided into an unsorted prefix and a heap-ordered suffix (initially empty).\nEach step shrinks the prefix and expands the suffix.\nWhen the prefix is empty, this phase is complete.\nDuring the second phase, the array is divided into a heap-ordered prefix and a sorted suffix (initially empty).\nEach step shrinks the prefix and expands the suffix.\nWhen the prefix is empty, the array is sorted.\n\n# Algorithm\nThe heapsort algorithm begins by rearranging the array into a binary max-heap.\nThe algorithm then repeatedly swaps the root of the heap (the greatest element remaining in the heap) with its last element, which is then declared to be part of the sorted suffix.\nThen the heap, which was damaged by replacing the root, is repaired so that the greatest element is again at the root.\nThis repeats until only one value remains in the heap.\nThe steps are:\nO(n)\noperations.\nThe heapify operation is run once, and is\nO(n)\nin performance.\nThe siftDown function is called n times and requires\nO(log n)\nwork each time, due to its traversal starting from the root node.\nTherefore, the performance of this algorithm is\nO(n + n log n) = O(n log n)\n.\nThe heart of the algorithm is the siftDown function.\nThis constructs binary heaps out of smaller heaps, and may be thought of in two equivalent ways:\nTo establish the max-heap property at the root, up to three nodes must be compared (the root and its two children), and the greatest must be made the root.\nThis is most easily done by finding the greatest child, then comparing that child to the root.\nThere are three cases:\nThe number of iterations in any one siftdown call is bounded by the height of the tree, which is\n⌊log2 n⌋ = O(log n)\n.\n\n## Pseudocode\nThe following is a simple way to implement the algorithm in [pseudocode](https://bliptext.com/articles/pseudocode).\nArrays are [zero-based](https://bliptext.com/articles/comparison-of-programming-languages-array) and swap is used to exchange two elements of the array.\nMovement 'down' means from the root towards the leaves, or from lower indices to higher.\nNote that during the sort, the largest element is at the root of the heap at a[0], while at the end of the sort, the largest element is in a[end].\n**procedure** heapsort(a, count) **is**\n**input:** an unordered array a of length count\n(Build the heap in array a so that largest value is at the root)\nheapify(a, count)\n(The following loop maintains the [invariants](https://bliptext.com/articles/loop-invariant) that a[0:end−1] is a heap, and every element a[end:count−1] beyond end is greater than everything before it, i.e. a[end:count−1] is in sorted order.)\nend ← count\n**while** end > 1 **do**\n(the heap size is reduced by one)\nend ← end − 1\n(a[0] is the root and largest value. The swap moves it in front of the sorted elements.)\nswap(a[end], a[0])\n(the swap ruined the heap property, so restore it)\nsiftDown(a, 0, end)\nThe sorting routine uses two subroutines, heapify and siftDown.\nThe former is the common in-place heap construction routine, while the latter is a common subroutine for implementing heapify.\n(Put elements of 'a' in heap order, in-place)\n**procedure** heapify(a, count) **is**\n(start is initialized to the first leaf node)\n(the last element in a 0-based array is at index count-1; find the parent of that element)\nstart ← iParent(count-1) + 1\n**while** start > 0 **do**\n(go to the last non-heap node)\nstart ← start − 1\n(sift down the node at index 'start' to the proper place such that all nodes below the start index are in heap order)\nsiftDown(a, start, count)\n(after sifting down the root all nodes/elements are in heap order)\n(Repair the heap whose root element is at index 'start', assuming the heaps rooted at its children are valid)\n**procedure** siftDown(a, root, end) **is**\n**while** iLeftChild(root) 1 **do**\n**if** start > 0 **then** (Heap construction)\nstart ← start − 1\n**else** (Heap extraction)\nend ← end − 1\nswap(a[end], a[0])\n(The following is siftDown(a, start, end))\nroot ← start\n**while** iLeftChild(root) 0\nparent := iParent(end)\n**if** a[parent] a[iLeftChild(j)] **then**\nj ← iRightChild(j)\n**else**\nj ← iLeftChild(j)\n(At the last level, there might be only one child)\n**if** iLeftChild(j) a[j] **do**\nj ← iParent(j)\n**while** j > i **do**\nswap(a[i], a[j])\nj ← iParent(j)\nBottom-up heapsort was announced as beating quicksort (with median-of-three pivot selection) on arrays of size ≥16000.\nA 2008 re-evaluation of this algorithm showed it to be no faster than top-down heapsort for integer keys, presumably because modern [branch prediction](https://bliptext.com/articles/branch-prediction) nullifies the cost of the predictable comparisons which bottom-up heapsort manages to avoid.\nA further refinement does a [binary search](https://bliptext.com/articles/binary-search) in the upward search, and sorts in a worst case of\n(n+1)(log2(n+1) + log2 log2(n+1) + 1.82) + O(log2n)\ncomparisons, approaching [the information-theoretic lower bound](https://bliptext.com/articles/comparison-sort) of\nn log2n − 1.4427n\ncomparisons.\nA variant which uses two extra bits per internal node (n−1 bits total for an n-element heap) to cache information about which child is greater (two bits are required to store three cases: left, right, and unknown) uses less than\nn log2n + 1.1n\ncompares.\n\n## Other variations\nn log2n + O(n)\ncomparisons.\nWhen the maximum is taken, rather than fill the vacated space with an unsorted data value, fill it with a\n−∞\nsentinel value, which never \"bounces\" back up.\nIt turns out that this can be used as a primitive in an in-place (and non-recursive) \"QuickHeapsort\" algorithm.\nFirst, you perform a quicksort-like partitioning pass, but reversing the order of the partitioned data in the array.\nSuppose ([without loss of generality](https://bliptext.com/articles/without-loss-of-generality)) that the smaller partition is the one greater than the pivot, which should go at the end of the array, but our reversed partitioning step places it at the beginning.\nForm a heap out of the smaller partition and do out-of-place heapsort on it, exchanging the extracted maxima with values from the end of the array.\nThese are less than the pivot, meaning less than any value in the heap, so serve as\n−∞\nsentinel values.\nOnce the heapsort is complete (and the pivot moved to just before the now-sorted end of the array), the order of the partitions has been reversed, and the larger partition at the beginning of the array may be sorted in the same way.\n(Because there is no non-[tail recursion](https://bliptext.com/articles/tail-recursion), this also eliminates quicksort's\nO(log n)\nstack usage.)\nO(n log n)\n. The advantage of smoothsort is that it comes closer to\nO(n)\ntime if the [input is already sorted to some degree](https://bliptext.com/articles/adaptive-sort), whereas heapsort averages\nO(n log n)\nregardless of the initial sorted state.\nDue to its complexity, smoothsort is rarely used.\nO(n)\ntime, and its root is placed in a 1-element binary heap.\nThen we repeatedly extract the minimum from the binary heap, output the tree's root element, and add its left and right children (if any) which are themselves Cartesian trees, to the binary heap.\nAs they show, 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\nO(n log n)\nfor inputs that are already nearly sorted.\nn log2 n+O(1)\ncomparisons in the worst case, close to the theoretical minimum, using one extra bit of state per node.\nWhile this extra bit makes the algorithms not truly in-place, if space for it can be found inside the element, these algorithms are simple and efficient, but still slower than binary heaps if key comparisons are cheap enough (e.g. integer keys) that a constant factor does not matter.\nn log2 n+O(1)\ncomparisons, and a similar number of element moves.\nIt is, however, even more complex and not justified unless comparisons are very expensive.\n\n# Comparison with other sorts\nHeapsort primarily competes with [quicksort](https://bliptext.com/articles/quicksort), another very efficient general purpose in-place unstable comparison-based sort algorithm.\nHeapsort's primary advantages are its simple, non-[recursive](https://bliptext.com/articles/recursion-computer-science) code, minimal auxiliary storage requirement, and reliably good performance: its best and worst cases are within a small constant factor of each other, and of the [theoretical lower bound on comparison sorts](https://bliptext.com/articles/comparison-sort).\nWhile it cannot do better than\nO(n log n)\nfor pre-sorted inputs, it does not suffer from quicksort's\nO(n2)\nworst case, either.\nReal-world quicksort implementations use a variety of [heuristics](https://bliptext.com/articles/heuristic) to avoid the worst case, but that makes their implementation far more complex, and implementations such as [introsort](https://bliptext.com/articles/introsort) and pattern-defeating quicksort use heapsort as a last-resort fallback if they detect degenerate behaviour.\nThus, their worst-case performance is slightly worse than if heapsort had been used from the beginning.\nHeapsort's primary disadvantages are its poor [locality of reference](https://bliptext.com/articles/locality-of-reference) and its inherently serial nature; the accesses to the implicit tree are widely scattered and mostly random, and there is no straightforward way to convert it to a [parallel algorithm](https://bliptext.com/articles/parallel-algorithm).\nThe worst-case performance guarantees make heapsort popular in [real-time computing](https://bliptext.com/articles/real-time-computing), and systems concerned with maliciously chosen inputs such as the Linux kernel.\nThe combination of small implementation and dependably [\"good enough\"](https://bliptext.com/articles/principle-of-good-enough) performance make it popular in [embedded systems](https://bliptext.com/articles/embedded-system), and generally any application where sorting is not a [performance bottleneck](https://bliptext.com/articles/bottleneck-software).\nE.g. heapsort is ideal for sorting a list of [filenames](https://bliptext.com/articles/filename) for display, but a [database management system](https://bliptext.com/articles/database-management-system) would probably want a more aggressively optimized sorting algorithm.\nA well-implemented quicksort is usually 2–3 times faster than heapsort.\nAlthough quicksort requires fewer comparisons, this is a minor factor.\n(Results claiming twice as many comparisons are measuring the top-down version; see .) The main advantage of quicksort is its much better locality of reference: partitioning is a linear scan with good spatial locality, and the recursive subdivision has good temporal locality.\nWith additional effort, quicksort can also be implemented in mostly [branch-free code](https://bliptext.com/articles/branch-free-code), and multiple CPUs can be used to sort subpartitions in parallel.\nThus, quicksort is preferred when the additional performance justifies the implementation effort.\nThe other major\nO(n log n)\nsorting algorithm is [merge sort](https://bliptext.com/articles/merge-sort), but that rarely competes directly with heapsort because it is not in-place.\nMerge sort's requirement for\nΩ(n)\nextra space (roughly half the size of the input) is usually prohibitive except in the situations where merge sort has a clear advantage:\n\n# Example\nThe examples sort the values { 6, 5, 3, 1, 8, 7, 2, 4 } in increasing order using both heap-construction algorithms.\nThe elements being compared are shown in a **bold** font.\nThere are typically two when sifting up, and three when sifting down, although there may be fewer when the top or bottom of the tree is reached.\n\n## Heap construction (Williams' algorithm)\n\n## Heap construction (Floyd's algorithm)\n\n## Heap extraction","revisionCount":0},"hasMore":false,"nextCursor":null}

History