7.8. Heap sort¶
Our discussion of Quicksort began by considering the practicality of using a BST for sorting. The BST requires more space than the other sorting methods and will be slower than Quicksort or Mergesort due to the relative expense of inserting values into the tree. There is also the possibility that the BST might be unbalanced, leading to a \(\Theta(n^2)\) worst-case running time. Subtree balance in the BST is closely related to Quicksort's partition step. Quicksort's pivot serves roughly the same purpose as the BST root value in that the left partition (subtree) stores values less than the pivot (root) value, while the right partition (subtree) stores values greater than or equal to the pivot (root).
A good sorting algorithm can be devised based on a tree structure more suited to the purpose. In particular, we would like the tree to be balanced, space efficient, and fast. The algorithm should take advantage of the fact that sorting is a special-purpose application in that all of the values to be stored are available at the start. This means that we do not necessarily need to insert one value at a time into the tree structure.
Heapsort is based on the heap data structure.
Heapsort has all of the advantages just listed.
The complete binary tree is balanced, its array representation is
space efficient, and we can load all values into the tree at once,
taking advantage of the efficient buildheap function.
7.8.1. Heap sort walkthrough¶
To sort in ascending order, first build a max-heap, where every parent is at least as large as its children. Then repeatedly exchange the root (the largest remaining value) with the last active heap item, shrink the heap by one, and sift down the replacement root. Sifting down exchanges a parent with its larger child until the heap property holds again or the value reaches a leaf.
The following stack uses our familiar array
[54, 26, 93, 17, 77, 31, 44, 55, 20]. Each scene shows the active
heap as a tree and the full array below it. Outlined nodes and cells
mark the values being compared or exchanged. The last_heap arrow
marks the last active cell, and the sorted arrow marks the start
of the sorted suffix. Values in that suffix remain in the array but
are excluded from the tree and all later heap operations.
Heap sort: build a max-heap, extract the maximum, and sift down
Scene 1: Begin with the original array.
The tree and array show the same nine values. The root is at index 0;
its children are at indices 1 and 2. For a parent at index p,
the children are at 2*p + 1 and 2*p + 2, when those indices
are within the active heap. This complete tree is not yet a max-heap.
Active heap (9 items)
Text description
Tree diagram with 9 visible nodes.
The root is “54”.
“54” has left child “26” and right child “93”. “26” has left child “17” and right child “77”. “93” has left child “31” and right child “44”. “17” has left child “55” and right child “20”.
“77”, “31”, “44”, “55”, and “20” are leaves.
Array
Text description
Array with 9 cells. From left to right: index 0: “54”, index 1: “26”, index 2: “93”, index 3: “17”, index 4: “77”, index 5: “31”, index 6: “44”, index 7: “55”, and index 8: “20”.
Indicator “last_heap” points to cell 8, value “20”.
Scene 2: Build the heap: exchange 17 with its larger child, 55.
Build a max-heap from the bottom up. Indices 4 through 8 are leaves, so their one-item subtrees already satisfy the heap property. Start with the last parent, index 3. Its children are 55 and 20. Exchange 17 with the larger child, 55. The value 17 reaches a leaf, ending this sift-down.
Active heap (9 items)
Text description
Tree diagram with 9 visible nodes.
The root is “54”.
“54” has left child “26” and right child “93”. “26” has left child “55” and right child “77”. “93” has left child “31” and right child “44”. “55” has left child “17” and right child “20”.
“77”, “31”, “44”, “17”, and “20” are leaves.
“55” and “17” are highlighted.
Array
Text description
Array with 9 cells. From left to right: index 0: “54”, index 1: “26”, index 2: “93”, index 3: “55”, index 4: “77”, index 5: “31”, index 6: “44”, index 7: “17”, and index 8: “20”.
index 3: “55” and index 7: “17” are highlighted.
Indicator “last_heap” points to cell 8, value “20”.
Scene 3: Check the parent at index 2: keep 93 in place.
Move left to index 2. Its children are 31 and 44. Since 93 is already greater than both children, this subtree needs no exchange.
Active heap (9 items)
Text description
Tree diagram with 9 visible nodes.
The root is “54”.
“54” has left child “26” and right child “93”. “26” has left child “55” and right child “77”. “93” has left child “31” and right child “44”. “55” has left child “17” and right child “20”.
“77”, “31”, “44”, “17”, and “20” are leaves.
“93”, “31”, and “44” are highlighted.
Array
Text description
Array with 9 cells. From left to right: index 0: “54”, index 1: “26”, index 2: “93”, index 3: “55”, index 4: “77”, index 5: “31”, index 6: “44”, index 7: “17”, and index 8: “20”.
index 2: “93”, index 5: “31”, and index 6: “44” are highlighted.
Indicator “last_heap” points to cell 8, value “20”.
Scene 4: Build the heap: exchange 26 with its larger child, 77.
At index 1, compare 26 with children 55 and 77. Exchange 26 with 77, the larger child. The value 26 reaches a leaf. Choosing the larger child ensures that the new parent is at least as large as both children.
Active heap (9 items)
Text description
Tree diagram with 9 visible nodes.
The root is “54”.
“54” has left child “77” and right child “93”. “77” has left child “55” and right child “26”. “93” has left child “31” and right child “44”. “55” has left child “17” and right child “20”.
“26”, “31”, “44”, “17”, and “20” are leaves.
“77” and “26” are highlighted.
Array
Text description
Array with 9 cells. From left to right: index 0: “54”, index 1: “77”, index 2: “93”, index 3: “55”, index 4: “26”, index 5: “31”, index 6: “44”, index 7: “17”, and index 8: “20”.
index 1: “77” and index 4: “26” are highlighted.
Indicator “last_heap” points to cell 8, value “20”.
Scene 5: Build the heap: exchange 54 with its larger child, 93.
Finally, sift down from the root. Compare 54 with children 77 and 93, then exchange it with 93. Continue checking 54 at index 2.
Active heap (9 items)
Text description
Tree diagram with 9 visible nodes.
The root is “93”.
“93” has left child “77” and right child “54”. “77” has left child “55” and right child “26”. “54” has left child “31” and right child “44”. “55” has left child “17” and right child “20”.
“26”, “31”, “44”, “17”, and “20” are leaves.
“93” and “54” are highlighted.
Array
Text description
Array with 9 cells. From left to right: index 0: “93”, index 1: “77”, index 2: “54”, index 3: “55”, index 4: “26”, index 5: “31”, index 6: “44”, index 7: “17”, and index 8: “20”.
index 0: “93” and index 2: “54” are highlighted.
Indicator “last_heap” points to cell 8, value “20”.
Scene 6: The max-heap is ready; 93 is at the root.
At index 2, 54 is greater than its children, 31 and 44, so stop. Every parent is now at least as large as its children, and the root holds the maximum value, 93. Building the heap does not sort the array: for example, 77 still appears before 54.
Active heap (9 items)
Text description
Tree diagram with 9 visible nodes.
The root is “93”.
“93” has left child “77” and right child “54”. “77” has left child “55” and right child “26”. “54” has left child “31” and right child “44”. “55” has left child “17” and right child “20”.
“26”, “31”, “44”, “17”, and “20” are leaves.
“54”, “31”, and “44” are highlighted.
Array
Text description
Array with 9 cells. From left to right: index 0: “93”, index 1: “77”, index 2: “54”, index 3: “55”, index 4: “26”, index 5: “31”, index 6: “44”, index 7: “17”, and index 8: “20”.
index 2: “54”, index 5: “31”, and index 6: “44” are highlighted.
Indicator “last_heap” points to cell 8, value “20”.
Scene 7: Exchange the maximum, 93, with the last heap value, 20.
Exchange the root at index 0 with the last active item at index 8. The maximum value, 93, is now in its final array position. The replacement root, 20, may violate the heap property.
Active heap (9 items)
Text description
Tree diagram with 9 visible nodes.
The root is “20”.
“20” has left child “77” and right child “54”. “77” has left child “55” and right child “26”. “54” has left child “31” and right child “44”. “55” has left child “17” and right child “93”.
“26”, “31”, “44”, “17”, and “93” are leaves.
“20” and “93” are highlighted.
Array
Text description
Array with 9 cells. From left to right: index 0: “20”, index 1: “77”, index 2: “54”, index 3: “55”, index 4: “26”, index 5: “31”, index 6: “44”, index 7: “17”, and index 8: “93”.
index 0: “20” and index 8: “93” are highlighted.
Indicator “last_heap” points to cell 8, value “93”.
Scene 8: Shrink the active heap to eight items.
Exclude index 8 from the heap. The value 93 stays in the array, but disappears from the active tree. The sorted suffix begins at index 8, and the last active heap item is now at index 7. Only the active heap participates in the next sift-down.
Active heap (8 items)
Text description
Tree diagram with 8 visible nodes.
The root is “20”.
“20” has left child “77” and right child “54”. “77” has left child “55” and right child “26”. “54” has left child “31” and right child “44”. “55” has left child “17”.
“26”, “31”, “44”, and “17” are leaves.
“20” is highlighted.
Array
Text description
Array with 9 cells. From left to right: index 0: “20”, index 1: “77”, index 2: “54”, index 3: “55”, index 4: “26”, index 5: “31”, index 6: “44”, index 7: “17”, and index 8: “93”.
index 0: “20” is highlighted.
Indicator “last_heap” points to cell 7, value “17”.
Indicator “sorted” points to cell 8, value “93”.
Scene 9: Restore the heap: exchange 20 with its larger child, 77.
The root's children are 77 and 54. Exchange 20 with 77, then continue sifting 20 down from index 1. The sorted value 93 stays in place.
Active heap (8 items)
Text description
Tree diagram with 8 visible nodes.
The root is “77”.
“77” has left child “20” and right child “54”. “20” has left child “55” and right child “26”. “54” has left child “31” and right child “44”. “55” has left child “17”.
“26”, “31”, “44”, and “17” are leaves.
“77” and “20” are highlighted.
Array
Text description
Array with 9 cells. From left to right: index 0: “77”, index 1: “20”, index 2: “54”, index 3: “55”, index 4: “26”, index 5: “31”, index 6: “44”, index 7: “17”, and index 8: “93”.
index 0: “77” and index 1: “20” are highlighted.
Indicator “last_heap” points to cell 7, value “17”.
Indicator “sorted” points to cell 8, value “93”.
Scene 10: Continue sifting down: exchange 20 with 55.
At index 1, the children are 55 and 26. Exchange 20 with the larger child, 55, and continue from index 3.
Active heap (8 items)
Text description
Tree diagram with 8 visible nodes.
The root is “77”.
“77” has left child “55” and right child “54”. “55” has left child “20” and right child “26”. “54” has left child “31” and right child “44”. “20” has left child “17”.
“26”, “31”, “44”, and “17” are leaves.
“55” and “20” are highlighted.
Array
Text description
Array with 9 cells. From left to right: index 0: “77”, index 1: “55”, index 2: “54”, index 3: “20”, index 4: “26”, index 5: “31”, index 6: “44”, index 7: “17”, and index 8: “93”.
index 1: “55” and index 3: “20” are highlighted.
Indicator “last_heap” points to cell 7, value “17”.
Indicator “sorted” points to cell 8, value “93”.
Scene 11: Stop at 20; the eight-item max-heap is restored.
At index 3, the only active child is 17 at index 7. The value 20 is greater than 17, so stop. Index 8 holds the sorted value 93 and is outside the heap. The new maximum, 77, is at the root.
Active heap (8 items)
Text description
Tree diagram with 8 visible nodes.
The root is “77”.
“77” has left child “55” and right child “54”. “55” has left child “20” and right child “26”. “54” has left child “31” and right child “44”. “20” has left child “17”.
“26”, “31”, “44”, and “17” are leaves.
“20” and “17” are highlighted.
Array
Text description
Array with 9 cells. From left to right: index 0: “77”, index 1: “55”, index 2: “54”, index 3: “20”, index 4: “26”, index 5: “31”, index 6: “44”, index 7: “17”, and index 8: “93”.
index 3: “20” and index 7: “17” are highlighted.
Indicator “last_heap” points to cell 7, value “17”.
Indicator “sorted” points to cell 8, value “93”.
Scene 12: Place 77 at index 7; shrink the heap to seven items.
Repeat the extraction: exchange root 77 with the last active value, 17, then exclude index 7 from the heap. The sorted suffix is now [77, 93]. Sift the replacement root, 17, down within indices 0 through 6.
Active heap (7 items)
Text description
Tree diagram with 7 visible nodes.
The root is “17”.
“17” has left child “55” and right child “54”. “55” has left child “20” and right child “26”. “54” has left child “31” and right child “44”.
“20”, “26”, “31”, and “44” are leaves.
“17” is highlighted.
Array
Text description
Array with 9 cells. From left to right: index 0: “17”, index 1: “55”, index 2: “54”, index 3: “20”, index 4: “26”, index 5: “31”, index 6: “44”, index 7: “77”, and index 8: “93”.
index 0: “17” and index 7: “77” are highlighted.
Indicator “last_heap” points to cell 6, value “44”.
Indicator “sorted” points to cell 7, value “77”.
Scene 13: Restore the heap: exchange 17 with 55.
The root's children are 55 and 54. Exchange 17 with the larger child, 55. Continue sifting 17 down from index 1.
Active heap (7 items)
Text description
Tree diagram with 7 visible nodes.
The root is “55”.
“55” has left child “17” and right child “54”. “17” has left child “20” and right child “26”. “54” has left child “31” and right child “44”.
“20”, “26”, “31”, and “44” are leaves.
“55” and “17” are highlighted.
Array
Text description
Array with 9 cells. From left to right: index 0: “55”, index 1: “17”, index 2: “54”, index 3: “20”, index 4: “26”, index 5: “31”, index 6: “44”, index 7: “77”, and index 8: “93”.
index 0: “55” and index 1: “17” are highlighted.
Indicator “last_heap” points to cell 6, value “44”.
Indicator “sorted” points to cell 7, value “77”.
Scene 14: Exchange 17 with 26; the seven-item heap is restored.
At index 1, the children are 20 and 26. Exchange 17 with 26. The value 17 reaches a leaf, so stop. The next maximum, 55, is now at the root.
Active heap (7 items)
Text description
Tree diagram with 7 visible nodes.
The root is “55”.
“55” has left child “26” and right child “54”. “26” has left child “20” and right child “17”. “54” has left child “31” and right child “44”.
“20”, “17”, “31”, and “44” are leaves.
“26” and “17” are highlighted.
Array
Text description
Array with 9 cells. From left to right: index 0: “55”, index 1: “26”, index 2: “54”, index 3: “20”, index 4: “17”, index 5: “31”, index 6: “44”, index 7: “77”, and index 8: “93”.
index 1: “26” and index 4: “17” are highlighted.
Indicator “last_heap” points to cell 6, value “44”.
Indicator “sorted” points to cell 7, value “77”.
Scene 15: Place 55 at index 6; shrink the heap to six items.
Exchange root 55 with the last active value, 44, and exclude index 6. The sorted suffix is [55, 77, 93]. The replacement root, 44, must be checked against children 26 and 54.
Active heap (6 items)
Text description
Tree diagram with 6 visible nodes.
The root is “44”.
“44” has left child “26” and right child “54”. “26” has left child “20” and right child “17”. “54” has left child “31”.
“20”, “17”, and “31” are leaves.
“44” is highlighted.
Array
Text description
Array with 9 cells. From left to right: index 0: “44”, index 1: “26”, index 2: “54”, index 3: “20”, index 4: “17”, index 5: “31”, index 6: “55”, index 7: “77”, and index 8: “93”.
index 0: “44” and index 6: “55” are highlighted.
Indicator “last_heap” points to cell 5, value “31”.
Indicator “sorted” points to cell 6, value “55”.
Scene 16: Exchange 44 with 54; the six-item heap is restored.
Exchange 44 with the larger child, 54. At index 2, its only active child is 31 at index 5. Since 44 is greater than 31, stop. The value 55 at index 6 is already sorted and cannot participate in this comparison.
Active heap (6 items)
Text description
Tree diagram with 6 visible nodes.
The root is “54”.
“54” has left child “26” and right child “44”. “26” has left child “20” and right child “17”. “44” has left child “31”.
“20”, “17”, and “31” are leaves.
“54” and “44” are highlighted.
Array
Text description
Array with 9 cells. From left to right: index 0: “54”, index 1: “26”, index 2: “44”, index 3: “20”, index 4: “17”, index 5: “31”, index 6: “55”, index 7: “77”, and index 8: “93”.
index 0: “54” and index 2: “44” are highlighted.
Indicator “last_heap” points to cell 5, value “31”.
Indicator “sorted” points to cell 6, value “55”.
Scene 17: Place 54 at index 5; shrink the heap to five items.
Exchange root 54 with the last active value, 31, then exclude index 5. The sorted suffix is [54, 55, 77, 93]. Compare the replacement root, 31, with children 26 and 44.
Active heap (5 items)
Text description
Tree diagram with 5 visible nodes.
The root is “31”.
“31” has left child “26” and right child “44”. “26” has left child “20” and right child “17”.
“44”, “20”, and “17” are leaves.
“31” is highlighted.
Array
Text description
Array with 9 cells. From left to right: index 0: “31”, index 1: “26”, index 2: “44”, index 3: “20”, index 4: “17”, index 5: “54”, index 6: “55”, index 7: “77”, and index 8: “93”.
index 0: “31” and index 5: “54” are highlighted.
Indicator “last_heap” points to cell 4, value “17”.
Indicator “sorted” points to cell 5, value “54”.
Scene 18: Exchange 31 with 44; the five-item heap is restored.
Exchange 31 with the larger child, 44. The value 31 reaches a leaf in the active heap, so stop. The root now holds the next maximum, 44.
Active heap (5 items)
Text description
Tree diagram with 5 visible nodes.
The root is “44”.
“44” has left child “26” and right child “31”. “26” has left child “20” and right child “17”.
“31”, “20”, and “17” are leaves.
“44” and “31” are highlighted.
Array
Text description
Array with 9 cells. From left to right: index 0: “44”, index 1: “26”, index 2: “31”, index 3: “20”, index 4: “17”, index 5: “54”, index 6: “55”, index 7: “77”, and index 8: “93”.
index 0: “44” and index 2: “31” are highlighted.
Indicator “last_heap” points to cell 4, value “17”.
Indicator “sorted” points to cell 5, value “54”.
Scene 19: Place 44 at index 4; shrink the heap to four items.
Exchange root 44 with the last active value, 17, then exclude index 4. The sorted suffix is [44, 54, 55, 77, 93]. Compare the replacement root, 17, with children 26 and 31.
Active heap (4 items)
Text description
Tree diagram with 4 visible nodes.
The root is “17”.
“17” has left child “26” and right child “31”. “26” has left child “20”.
“31” and “20” are leaves.
“17” is highlighted.
Array
Text description
Array with 9 cells. From left to right: index 0: “17”, index 1: “26”, index 2: “31”, index 3: “20”, index 4: “44”, index 5: “54”, index 6: “55”, index 7: “77”, and index 8: “93”.
index 0: “17” and index 4: “44” are highlighted.
Indicator “last_heap” points to cell 3, value “20”.
Indicator “sorted” points to cell 4, value “44”.
Scene 20: Exchange 17 with 31; the four-item heap is restored.
Exchange 17 with the larger child, 31. The value 17 reaches a leaf, so stop. The remaining active values form a max-heap with 31 at the root.
Active heap (4 items)
Text description
Tree diagram with 4 visible nodes.
The root is “31”.
“31” has left child “26” and right child “17”. “26” has left child “20”.
“17” and “20” are leaves.
“31” and “17” are highlighted.
Array
Text description
Array with 9 cells. From left to right: index 0: “31”, index 1: “26”, index 2: “17”, index 3: “20”, index 4: “44”, index 5: “54”, index 6: “55”, index 7: “77”, and index 8: “93”.
index 0: “31” and index 2: “17” are highlighted.
Indicator “last_heap” points to cell 3, value “20”.
Indicator “sorted” points to cell 4, value “44”.
Scene 21: Place 31 at index 3; shrink the heap to three items.
Exchange root 31 with the last active value, 20, then exclude index 3. The sorted suffix is [31, 44, 54, 55, 77, 93]. The replacement root, 20, has children 26 and 17.
Active heap (3 items)
Text description
Tree diagram with 3 visible nodes.
The root is “20”.
“20” has left child “26” and right child “17”.
“26” and “17” are leaves.
“20” is highlighted.
Array
Text description
Array with 9 cells. From left to right: index 0: “20”, index 1: “26”, index 2: “17”, index 3: “31”, index 4: “44”, index 5: “54”, index 6: “55”, index 7: “77”, and index 8: “93”.
index 0: “20” and index 3: “31” are highlighted.
Indicator “last_heap” points to cell 2, value “17”.
Indicator “sorted” points to cell 3, value “31”.
Scene 22: Exchange 20 with 26; the three-item heap is restored.
Exchange 20 with the larger child, 26. The value 20 reaches a leaf, so stop. The next maximum is 26.
Active heap (3 items)
Text description
Tree diagram with 3 visible nodes.
The root is “26”.
“26” has left child “20” and right child “17”.
“20” and “17” are leaves.
“26” and “20” are highlighted.
Array
Text description
Array with 9 cells. From left to right: index 0: “26”, index 1: “20”, index 2: “17”, index 3: “31”, index 4: “44”, index 5: “54”, index 6: “55”, index 7: “77”, and index 8: “93”.
index 0: “26” and index 1: “20” are highlighted.
Indicator “last_heap” points to cell 2, value “17”.
Indicator “sorted” points to cell 3, value “31”.
Scene 23: Place 26 at index 2; shrink the heap to two items.
Exchange root 26 with the last active value, 17, then exclude index 2. The sorted suffix is [26, 31, 44, 54, 55, 77, 93]. The replacement root, 17, has just one active child, 20.
Active heap (2 items)
Text description
Tree diagram with 2 visible nodes.
The root is “17”.
“17” has left child “20”.
“20” is a leaf.
“17” is highlighted.
Array
Text description
Array with 9 cells. From left to right: index 0: “17”, index 1: “20”, index 2: “26”, index 3: “31”, index 4: “44”, index 5: “54”, index 6: “55”, index 7: “77”, and index 8: “93”.
index 0: “17” and index 2: “26” are highlighted.
Indicator “last_heap” points to cell 1, value “20”.
Indicator “sorted” points to cell 2, value “26”.
Scene 24: Exchange 17 with 20; the two-item heap is restored.
Exchange 17 with its only child, 20. The heap property holds again, with 20 at the root.
Active heap (2 items)
Text description
Tree diagram with 2 visible nodes.
The root is “20”.
“20” has left child “17”.
“17” is a leaf.
“20” and “17” are highlighted.
Array
Text description
Array with 9 cells. From left to right: index 0: “20”, index 1: “17”, index 2: “26”, index 3: “31”, index 4: “44”, index 5: “54”, index 6: “55”, index 7: “77”, and index 8: “93”.
index 0: “20” and index 1: “17” are highlighted.
Indicator “last_heap” points to cell 1, value “17”.
Indicator “sorted” points to cell 2, value “26”.
Scene 25: Place 20 at index 1; only 17 remains in the heap.
Exchange root 20 with the last active value, 17, then exclude index 1. A one-item heap needs no sift-down. The remaining value, 17, must be the smallest and is already in its final position.
Active heap (1 item)
Text description
Tree diagram with 1 visible node.
The root is “17”.
“17” is a leaf.
“17” is highlighted.
Array
Text description
Array with 9 cells. From left to right: index 0: “17”, index 1: “20”, index 2: “26”, index 3: “31”, index 4: “44”, index 5: “54”, index 6: “55”, index 7: “77”, and index 8: “93”.
index 0: “17” and index 1: “20” are highlighted.
Indicator “last_heap” points to cell 0, value “17”.
Indicator “sorted” points to cell 1, value “20”.
Scene 26: The array is sorted in ascending order.
Treat the final value, 17, as sorted too. The active heap is empty, and the full array is [17, 20, 26, 31, 44, 54, 55, 77, 93]. Each extraction placed the largest remaining value immediately before the sorted suffix. All exchanges took place in the original array; the tree was another view of those same values.
Array
Text description
Array with 9 cells. From left to right: index 0: “17”, index 1: “20”, index 2: “26”, index 3: “31”, index 4: “44”, index 5: “54”, index 6: “55”, index 7: “77”, and index 8: “93”.
Indicator “sorted” points to cell 0, value “17”.
7.8.2. Heap sort analysis¶
The asymptotic performance of Heapsort when all of the records have unique key values is \(\Theta(n \log n)\) in the best, average, and worst cases. It is not as fast as Quicksort in the average case (by a constant factor), but Heapsort has special properties that will make it particularly useful for external sorting algorithms - used when sorting data sets too large to fit in main memory.
The following animations show heap sort in action. Yellow marks the active root or subtree parent, red marks compared or exchanged values, teal marks the active heap boundary, purple marks the completed max heap, and gray marks the sorted suffix.
More to Explore