Why this matters
Sorting is the task you will meet most often in coding interviews and in real programs. You already know two simple sorts from this module, bubble sort and insertion sort. Both are easy to write, but they become slow when the list is long, because each step can move one value only a short distance. Merge sort and quick sort are much faster, but merge sort needs a second list of the same size, and quick sort can become slow on bad input.
Heap sort is the third fast option. It runs in O(n log n) time. The work grows roughly as n times log2 n, where log2 n is the number of times you can halve n before you reach 1. It also needs O(1) extra space, which means it needs only a few variables on top of the list you are sorting. It does all its work by swapping values inside the same list. That makes it a good tool when memory is tight.
This lesson covers the heap sort algorithm and how to write it in C++. It assumes you know arrays and vectors, and that you have written a loop and a function. It uses the idea of a heap and shows how to build and use one for sorting. The heap as a data structure, with its own insert and remove operations, is covered in the heaps module. Here you only need the heap rule and the way the list is laid out in memory.
The idea in plain words
A heap is a way of arranging values so that the largest value is always easy to find. In a max-heap, every parent value is at least as large as the values below it. The largest value of the whole heap sits at the top, which we call the root. That is the only fact about a heap you need for heap sort.
Think of a company with a boss. In a max-heap, the boss is always the largest number, and each person is no larger than the person above them. The boss is always the biggest, but two people on the same level can be in any order. The heap does not say which of two children is larger. It only says that each child is smaller than its parent.
You do not need a tree of nodes and pointers to use a heap. A heap can live in a plain vector, and the position of each value tells you its parent and children. The rule is simple. For a value at index i:
- the left child is at index
2 * i + 1 - the right child is at index
2 * i + 2 - the parent is at index
(i - 1) / 2, using whole-number division
Here is a small example. Take the vector {10, 5, 3, 4, 1}. Index 0 holds 10, the root. Its children are at indexes 1 and 2, which hold 5 and 3. Index 1 has its own children at indexes 3 and 4, which hold 4 and 1. Each parent is at least as large as each child, so this vector is a valid max-heap.
// Index: 0 1 2 3 4
std::vector<int> a = {10, 5, 3, 4, 1};
// a[0] = 10 is the root, and it is the largest value.
// The children of a[1] = 5 are a[3] = 4 and a[4] = 1.The heap rule does not say that the whole vector is sorted. The vector {10, 5, 3, 4, 1} is not sorted, but it is a heap. A heap only promises that the root is the largest. Heap sort uses that one promise over and over, and each time it adds one more value to the sorted part at the end.
Why the layout works
The index rules come from a simple picture. Draw the values as a tree with the root at the top. Put the root at index 0. Put its two children on the next level at indexes 1 and 2. Put the four values on the level after that at indexes 3 to 6, and so on. Read the tree one level at a time, left to right, and you get the vector in order. Each level is full before the next one starts, except possibly the last level. A tree like this is called complete.
Because each level is full, you never have gaps in the vector. That is why the index formulas work. Take index 5. Its parent is (5 - 1) / 2, which is 2. Going the other way, the children of index 2 are 2 * 2 + 1, which is 5, and 2 * 2 + 2, which is 6. So index 5 is the left child of index 2.
Step 1: fix one parent
Heap sort depends on one small operation. Given a value at index i, assume that both of its subtrees already follow the heap rule. Then compare the value with its two children. If the value is smaller than the larger child, swap them. Then keep going down from the position where the value landed, until it is no smaller than its children or it has no children left. This operation is called sift down, because the value sinks down the tree until it reaches the right level.
Here is a worked example with the vector {3, 9, 5}. Index 0 holds 3. Its children are index 1 (value 9) and index 2 (value 5). The larger child is 9, so 3 and 9 swap. The vector is now {9, 3, 5}. The value 3 is now at index 1. Its children would be at indexes 3 and 4, which are outside the vector, so 3 has no children and the sinking stops.
#include <cstddef>
#include <utility>
#include <vector>
// Sink the value at index i until the heap rule holds below it.
// Only the first `size` elements count as part of the heap.
void sift_down(std::vector<int>& a, std::size_t size, std::size_t i) {
while (true) {
std::size_t largest = i;
std::size_t left = 2 * i + 1;
std::size_t right = 2 * i + 2;
if (left < size && a[left] > a[largest]) largest = left;
if (right < size && a[right] > a[largest]) largest = right;
if (largest == i) return;
std::swap(a[i], a[largest]);
i = largest;
}
}The loop does three things in each round. It finds the largest of three values: the current value and its two children. If the current value is the largest, the job is done, and the function returns. Otherwise it swaps the value with the largest child, and it moves its index to the child's index. The next round checks the value in its new place.
The check left < size is the safety rule. Children that are past the end of the heap do not exist, so the code must not read them. The word size is the number of values that still belong to the heap. It is not always the length of the vector, as you will see in the next steps. Keeping the two numbers separate is the key idea in this lesson.
Each round moves the value down one level. A heap with n values has about log2(n) levels, so one sift down takes at most about log2(n) rounds. For a vector of one million values, that is about 20 rounds, not one million.
Step 2: build the heap
Now take an unsorted vector and make it a heap. You can do this with one sift down per parent, starting from the last parent and moving back toward the root. The leaves at the bottom of the tree are already heaps by themselves, because a single value has no children to break the rule. So you only need to sift the values that have children.
In a vector of n values, the last parent has index n / 2 - 1 when n is at least 2. Here is the loop, using a trick that avoids negative indexes. The counter starts at n / 2. The check i-- > 0 compares the old value with 0, and then lowers the counter. The loop body therefore sees n / 2 - 1 first, then n / 2 - 2, and so on, down to 0.
void build_max_heap(std::vector<int>& a) {
std::size_t n = a.size();
for (std::size_t i = n / 2; i-- > 0;) {
sift_down(a, n, i);
}
}Work through the vector {4, 10, 3, 5, 1}. Here n is 5, so n / 2 is 2, and the loop visits indexes 1 and then 0.
At index 1 the value is 10. Its children are at indexes 3 (value 5) and 4 (value 1). Index 1 is already larger than both, so nothing moves. At index 0 the value is 4. Its children are index 1 (value 10) and index 2 (value 3). The larger child is 10, so 4 and 10 swap, giving {10, 4, 3, 5, 1}. The value 4 is now at index 1, with children 5 and 1. The larger child is 5, so 4 and 5 swap, giving {10, 5, 3, 4, 1}. Now the value 4 has no children, and the heap is complete.
After the build, the largest value, 10, is at the root. Every parent is at least as large as its children. This is the state you need before the sorting step begins.
Why build from the bottom
You might ask why the loop starts at the last parent and not at the root. The answer is that a sift down only works when both subtrees below the value already obey the heap rule. Starting at the bottom makes this true. When you reach a value, every value below it has already been fixed. Starting at the root would break this promise, because the values below might still be out of place.
Step 3: move the top to the end
Now the sorting step. The root holds the largest value of the heap. Swap it with the last value in the heap. The largest value is now in its final place, at the end of the vector, and it will never move again. The heap is one value smaller. The value that came from the end is now at the root, and it is probably too small for that position. Sift it down to restore the heap rule. Then repeat with the new root.
After every round, the heap gets one value smaller, and the sorted part at the end of the vector gets one value bigger. When the heap has only one value left, it is already in place, so the sort is done.
void heap_sort(std::vector<int>& a) {
std::size_t n = a.size();
for (std::size_t i = n / 2; i-- > 0;) {
sift_down(a, n, i);
}
for (std::size_t end = n; end > 1; --end) {
std::swap(a[0], a[end - 1]);
sift_down(a, end - 1, 0);
}
}The second loop is where the two sizes meet. The variable end counts how many values are still in the heap. The swap uses a[end - 1], which is the last value of the heap, and the sift uses end - 1 as the new heap size. The values from end - 1 to the end of the vector are the sorted part, and the code never reads them again except through the swap.
The loop stops when end is 1. A heap of one value needs no work. Starting end at n and stopping at 1 means the loop runs n - 1 times.
A full trace with a small array
Watching every step is the best way to understand heap sort. The program below is the same algorithm with one extra function that prints the vector after each step. The vertical bar | marks the boundary between the heap, on the left, and the sorted values, on the right.
#include <cstddef>
#include <iostream>
#include <utility>
#include <vector>
void print(const char* label, const std::vector<int>& a, std::size_t heap_size) {
std::cout << label << ": ";
for (std::size_t i = 0; i < a.size(); ++i) {
if (i == heap_size) std::cout << "| ";
std::cout << a[i] << ' ';
}
std::cout << '\n';
}
void sift_down(std::vector<int>& a, std::size_t size, std::size_t i) {
while (true) {
std::size_t largest = i;
std::size_t left = 2 * i + 1;
std::size_t right = 2 * i + 2;
if (left < size && a[left] > a[largest]) largest = left;
if (right < size && a[right] > a[largest]) largest = right;
if (largest == i) return;
std::swap(a[i], a[largest]);
i = largest;
}
}
void heap_sort(std::vector<int>& a) {
std::size_t n = a.size();
for (std::size_t i = n / 2; i-- > 0;) {
sift_down(a, n, i);
print(" sift index", a, n);
}
print("heap built ", a, n);
for (std::size_t end = n; end > 1; --end) {
std::swap(a[0], a[end - 1]);
print(" swap top", a, end - 1);
sift_down(a, end - 1, 0);
}
}
int main() {
std::vector<int> a = {4, 10, 3, 5, 1};
heap_sort(a);
print("result ", a, a.size());
}Compile it and run it:
g++ -std=c++20 -Wall heap_trace.cpp -o heap_trace
./heap_traceThe output is:
sift index: 4 10 3 5 1
sift index: 10 5 3 4 1
heap built : 10 5 3 4 1
swap top: 1 5 3 4 | 10
swap top: 1 4 3 | 5 10
swap top: 3 1 | 4 5 10
swap top: 1 | 3 4 5 10
result : 1 3 4 5 10 Read the output in order. The first line is the vector after the sift at index 1. Nothing moves there, because 10 is already larger than its children 5 and 1. The second line is after the sift at index 0, where the 4 sinks past 10 and then past 5. The third line is the finished heap, with 10 at the root.
The swap lines show the sorting step. The first swap line shows the vector after the swap and before the sift. The 10 is at the end, and the 1 is at the root. The sift then moves the 1 down. It swaps with the 5 at index 0, then with the 4 at index 1, and it stops at index 3. After that sift the heap is 5 4 3 1, with 5 on top, and the second swap line shows that 5 moving to the end. Each following swap moves the next largest value to the end, and the final line holds the sorted vector.
Example 2: a descending sort
The algorithm works on any order you can express as a comparison. The default < in the earlier code means ascending order. If you want descending order, the heap should keep the smallest value at the top, and the easiest way to get that is to change the comparison. C++ provides std::greater<> for this. It is a function object, which means a value you can pass to a function. Calling it with a and b gives a > b.
To use a comparison in the code, make the functions take a parameter named comp and call it. The heap then uses comp(x, y) wherever it used x < y before. The rule to remember is this. comp(x, y) is true when x should come before y in the final order. The heap treats the value for which the comparison is largest as the top. With std::less, that is the largest value. With std::greater, that is the smallest value.
The template below does exactly this. It works for any type that the comparison can handle.
#include <cstddef>
#include <functional>
#include <iostream>
#include <utility>
#include <vector>
template <typename T, typename Compare>
void sift_down(std::vector<T>& a, std::size_t size, std::size_t i, Compare comp) {
while (true) {
std::size_t top = i;
std::size_t left = 2 * i + 1;
std::size_t right = 2 * i + 2;
if (left < size && comp(a[top], a[left])) top = left;
if (right < size && comp(a[top], a[right])) top = right;
if (top == i) return;
std::swap(a[i], a[top]);
i = top;
}
}
template <typename T, typename Compare = std::less<>>
void heap_sort(std::vector<T>& a, Compare comp = {}) {
std::size_t n = a.size();
for (std::size_t i = n / 2; i-- > 0;) sift_down(a, n, i, comp);
for (std::size_t end = n; end > 1; --end) {
std::swap(a[0], a[end - 1]);
sift_down(a, end - 1, 0, comp);
}
}
int main() {
std::vector<int> nums = {12, 4, 9, 4, 27, 1};
heap_sort(nums, std::greater<>{});
std::cout << "descending:";
for (int x : nums) std::cout << ' ' << x;
std::cout << '\n';
}The output is:
descending: 27 12 9 4 4 1The comparison comp(a[top], a[left]) is a[top] < a[left] when the comparison is std::less<>, and it is a[top] > a[left] when the comparison is std::greater<>. The code did not change between the two orders. Only the comparison changed. That is why a single function can sort in both directions.
The template also gives a default. The line Compare comp = {} means that if the caller does not pass a comparison, the default std::less<> is used, which is ascending order. The call heap_sort(nums) therefore sorts ascending.
Example 3: sorting records by one field
Real data is rarely a list of plain numbers. A list of players might hold a name and a score for each one. Heap sort needs only one thing from the values: a way to compare two of them. You can write a small function, called a lambda, that compares one field.
A lambda is a short unnamed function written in place. It starts with [], then lists its parameters in parentheses, then gives its body in braces. The lambda below compares the score field of two players. The rest of the code is the same heap sort, with a different comparison.
#include <cstddef>
#include <iostream>
#include <string>
#include <utility>
#include <vector>
template <typename T, typename Compare>
void sift_down(std::vector<T>& a, std::size_t size, std::size_t i, Compare comp) {
while (true) {
std::size_t top = i;
std::size_t left = 2 * i + 1;
std::size_t right = 2 * i + 2;
if (left < size && comp(a[top], a[left])) top = left;
if (right < size && comp(a[top], a[right])) top = right;
if (top == i) return;
std::swap(a[i], a[top]);
i = top;
}
}
template <typename T, typename Compare>
void heap_sort(std::vector<T>& a, Compare comp) {
std::size_t n = a.size();
for (std::size_t i = n / 2; i-- > 0;) sift_down(a, n, i, comp);
for (std::size_t end = n; end > 1; --end) {
std::swap(a[0], a[end - 1]);
sift_down(a, end - 1, 0, comp);
}
}
struct Player {
std::string name;
int score;
};
int main() {
std::vector<Player> players = {
{"Asha", 310}, {"Ravi", 120}, {"Meera", 450}, {"Dev", 275},
};
heap_sort(players, [](const Player& a, const Player& b) {
return a.score < b.score;
});
std::cout << "by score:";
for (const Player& p : players) std::cout << ' ' << p.name << '=' << p.score;
std::cout << '\n';
}The output is:
by score: Ravi=120 Dev=275 Asha=310 Meera=450The Player struct holds two fields, and the vector stores whole players. The heap moves the players around by swapping them, and the lambda decides their order by looking only at the score. The std::swap call works on any type that can be copied or moved, so it moves the whole player, name and all.
Passing the lambda to heap_sort is the same as passing std::greater<>{} in the previous example. Both are values that the heap calls like a function. The heap does not know or care what the comparison does.
When the records have a big body
Each swap copies the whole record, so a large struct makes every swap slower. A common fix is to sort a vector of indexes, or to store pointers to the records, and to swap those small values instead. This lesson does not cover that approach. The idea to keep is that heap sort does many swaps, and the cost of each swap depends on the size of the values being swapped.
Why heap sort is not stable
A sort is stable when two values that compare as equal keep their original order. Heap sort is not stable. The reason is that the swaps move values past each other, including values that compare as equal. Nothing in the algorithm checks the original order of equal values.
Here is a test. Each item has a key and a letter tag. The keys are compared, and the tags show the original order. Five items have key 5, and their tags are a, b, c and e. A stable sort keeps them in the order a, b, c, e. Heap sort does not.
#include <algorithm>
#include <cstddef>
#include <functional>
#include <iostream>
#include <utility>
#include <vector>
template <typename T, typename Compare>
void sift_down(std::vector<T>& a, std::size_t size, std::size_t i, Compare comp) {
while (true) {
std::size_t top = i;
std::size_t left = 2 * i + 1;
std::size_t right = 2 * i + 2;
if (left < size && comp(a[top], a[left])) top = left;
if (right < size && comp(a[top], a[right])) top = right;
if (top == i) return;
std::swap(a[i], a[top]);
i = top;
}
}
template <typename T, typename Compare>
void heap_sort(std::vector<T>& a, Compare comp) {
std::size_t n = a.size();
for (std::size_t i = n / 2; i-- > 0;) sift_down(a, n, i, comp);
for (std::size_t end = n; end > 1; --end) {
std::swap(a[0], a[end - 1]);
sift_down(a, end - 1, 0, comp);
}
}
struct Item {
int key;
char tag;
};
int main() {
std::vector<Item> items = {{5, 'a'}, {5, 'b'}, {5, 'c'}, {1, 'd'}, {5, 'e'}, {3, 'f'}};
heap_sort(items, [](const Item& x, const Item& y) { return x.key < y.key; });
for (const Item& it : items) std::cout << it.key << it.tag << ' ';
std::cout << '\n';
std::vector<Item> items2 = {{5, 'a'}, {5, 'b'}, {5, 'c'}, {1, 'd'}, {5, 'e'}, {3, 'f'}};
std::stable_sort(items2.begin(), items2.end(),
[](const Item& x, const Item& y) { return x.key < y.key; });
for (const Item& it : items2) std::cout << it.key << it.tag << ' ';
std::cout << '\n';
}The output is:
1d 3f 5c 5e 5b 5a
1d 3f 5a 5b 5c 5e The first line is heap sort. The keys are in order, but the five 5s are in the order c, e, b, a. The second line is std::stable_sort, and its five 5s stay in the order a, b, c, e.
This matters when you sort in two steps, which is the topic of the next lesson on multi-key sorting. If the order of equal values carries information, use a stable sort. If it does not, heap sort is a good choice when you need a fast sort with little extra memory.
Speed and memory
The heap sort running time has three parts. Building the heap takes O(n) time in total, although this is not obvious at first, because most values sit near the bottom and sink only a short distance. The sorting step runs n - 1 times, and each sift down takes about log2(n) rounds, so the sorting step takes O(n log n) time. The total time is O(n log n) in the best, average and worst cases. This is one of the main reasons people use heap sort. Quick sort can be slow on bad input, but heap sort is not.
The extra space is O(1). The sort works inside the vector you pass in. It needs a few variables for the loop counters, the sizes and the indexes, and these do not grow with n. Merge sort, by comparison, needs a second array of size n. Note that the names O(n log n) and O(1) describe how the work grows as the input grows, not an exact number of seconds. For a list of ten values, insertion sort might be faster than heap sort, because heap sort has more setup work. For a list of millions of values, heap sort's growth rate wins.
Heap sort also does not care whether the input is already sorted, nearly sorted or in reverse order. The work is about the same for every input of the same size. Insertion sort, by contrast, is very fast on nearly sorted data and slow on reversed data. That makes heap sort a steady choice when you cannot predict the input.
Common mistakes
The most common mistake is passing a plain C++ array to a function that expects a vector. The function signature is void heap_sort(std::vector<int>& a), and an array such as int arr[5] is a different type. Here is the error from g++ 15.2.0, using a small file that makes the mistake:
#include <vector>
void heap_sort(std::vector<int>& a);
int main() {
int arr[5] = {4, 10, 3, 5, 1};
heap_sort(arr);
}heap_err.cpp: In function ‘int main()’:
heap_err.cpp:7:15: error: invalid initialization of reference of type ‘std::vector<int>&’ from expression of type ‘int [5]’
7 | heap_sort(arr);
| ^~~
heap_err.cpp:3:34: note: in passing argument 1 of ‘void heap_sort(std::vector<int>&)’
3 | void heap_sort(std::vector<int>& a);
| ~~~~~~~~~~~~~~~~~~^The message says the function expects a std::vector<int>& and got an int [5]. The fix is to change the call to use a vector, as in std::vector<int> arr = {4, 10, 3, 5, 1};, or to write the function for a type that accepts both. Using a vector also avoids the other problems with plain arrays that the arrays module covers.
The second mistake is to use the full vector size inside sift_down instead of the heap size. This is the bug that breaks the algorithm without any error message. Here is a version of heap sort where sift_down reads a.size():
void sift_down_bad(std::vector<int>& a, std::size_t, std::size_t i) {
std::size_t size = a.size(); // wrong: this is the whole vector
while (true) {
std::size_t largest = i;
std::size_t left = 2 * i + 1;
std::size_t right = 2 * i + 2;
if (left < size && a[left] > a[largest]) largest = left;
if (right < size && a[right] > a[largest]) largest = right;
if (largest == i) return;
std::swap(a[i], a[largest]);
i = largest;
}
}With this bug, a sift down can pull a sorted value from the end of the vector back into the heap. Using this sift_down_bad in the heap_sort from this lesson, on {4, 10, 3, 5, 1}, prints a result that is not sorted:
10 5 3 4 1 The program compiles without warnings and finishes normally. It only gives the wrong answer. The fix is to pass the heap size as a separate parameter, as the code in this lesson does, and to make sure the sort step passes end - 1 and not a.size().
The third mistake is a loop that never ends because of an unsigned counter. The build loop could be written as for (std::size_t i = n / 2 - 1; i >= 0; --i). The test i >= 0 is always true for an unsigned type, because an unsigned number cannot be negative. When i reaches 0 and is decremented, it wraps around to the largest value the type can hold, and the loop keeps going. Here is a program that uses this loop. It has a guard so that the bad call runs only when a command-line argument is given:
#include <cstddef>
#include <iostream>
#include <vector>
void sift_down(std::vector<int>&, std::size_t, std::size_t) {}
void build_bad(std::vector<int>& a) {
std::size_t n = a.size();
for (std::size_t i = n / 2 - 1; i >= 0; --i) sift_down(a, n, i);
}
int main(int argc, char**) {
if (argc > 1) {
std::vector<int> b = {4, 10, 3};
build_bad(b);
}
std::cout << "done\n";
}Running the program with no argument prints done and exits. Running it with one argument never finishes. Here is what happened when it was run with a two-second limit:
g++ -std=c++20 -Wall heap_bugs.cpp -o heap_bugs
timeout 2 ./heap_bugs x
echo "exit $?"exit 124The exit code 124 comes from timeout, which stops a program that runs past its time limit. The fix is to count down with a signed type, or to count up and stop before the start, as the code in this lesson does with i-- > 0. The -Wall flag did not warn about this loop in g++ 15.2.0, so you have to check the loop by reading it.
The fourth mistake is to expect heap sort to keep equal values in their original order. The earlier stability test showed that it does not. If your data needs that order, use std::stable_sort, which the next lesson uses for multi-key sorting.
Practice
Exercise 1: build and sift by hand
Start with the vector {2, 9, 4, 7}. Build the max-heap with the build loop, writing down the vector after the build. Then swap the root with the last value, and sift the new root down in a heap of size 3. Write the vector after the sift.
Show the answer
After the build the vector is {9, 7, 4, 2}. The build visits index 1 first, where 9 is larger than its child 7, so nothing moves. Then it visits index 0. The value 2 swaps with 9, and then with 7, giving {9, 7, 4, 2}. After the swap of index 0 and index 3 the vector is {2, 7, 4, 9}. In a heap of size 3, the value 2 has children 7 and 4. It swaps with 7, and then it has no children inside the heap. The vector after the sift is {7, 2, 4, 9}. The last value, 9, is the sorted part.
Exercise 2: empty and one-value inputs
What does heap_sort do with an empty vector, and with a vector that holds only the value 5? Explain why neither case needs a special check in the code.
Show the answer
With an empty vector, n is 0. The build loop starts at n / 2, which is 0, and the check i-- > 0 is false at once, so the loop does not run. The sort loop starts at end = 0, and end > 1 is false, so it does not run either. With one value, n is 1, n / 2 is 0, and the build loop does not run. The sort loop starts at end = 1, and end > 1 is false. The vector is returned unchanged. Both cases are correct without a special check, because the loop conditions already skip all the work.
Exercise 3: find the bug
A student wrote this loop for the sorting step. It looks reasonable, but the output is wrong. Find the bug and say how to fix it.
for (std::size_t end = n; end > 1; --end) {
std::swap(a[0], a[end - 1]);
sift_down(a, n, 0);
}Show the answer
The sift call passes n, which is the whole size, instead of end - 1, which is the size of the heap. After each swap, the sift can move a value from the sorted part at the end back into the heap, because n still includes those values. The sorted values then move around and the output is no longer sorted. The fix is to pass end - 1 as the heap size: sift_down(a, end - 1, 0);. With the bug and the input {4, 10, 3, 5, 1}, the program prints 10 5 3 4 1, which is not sorted.
Exercise 4: sort strings by length
Use the template version of heap_sort to sort the strings "tea", "banana", "fig", "cherry" and "kiwi" from shortest to longest. Write the lambda that compares the lengths. Then say why "tea" and "fig" might come out in either order.
Show the answer
The lambda is [](const std::string& x, const std::string& y) { return x.size() < y.size(); }. The program prints tea fig kiwi cherry banana. The words "tea" and "fig" both have length 3, and "cherry" and "banana" both have length 6. Heap sort is not stable, so their order depends on the swaps, not on their order in the input. If the order of equal lengths matters, use std::stable_sort with the same lambda.
Exercise 5: count the swaps in a small heap
Build the heap for {1, 2, 3, 4, 5, 6, 7} by hand, and count how many swaps the build step makes. Use the index rules from this lesson. Then say whether the build step made any swap at the leaves.
Show the answer
The vector has 7 values, so the build loop starts at 7 / 2, which is 3, and visits indexes 2, 1 and 0. Index 2 holds 3, with children 6 and 7 at indexes 5 and 6. The child 7 is larger, so 3 and 7 swap: one swap. Index 1 holds 2, with children 4 and 5 at indexes 3 and 4. The child 5 is larger, so 2 and 5 swap: one swap. Then the value 2 is at index 4, which has no children inside a heap of size 7, so the sift stops. Index 0 holds 1, with children 5 and 7 at indexes 1 and 2. The vector is now {1, 5, 7, 4, 2, 6, 3}. The child 7 is larger, so 1 and 7 swap: one swap, and the value 1 is now at index 2 with children 6 and 3 at indexes 5 and 6. The child 6 is larger, so 1 and 6 swap: one more swap. The build makes 4 swaps in total. The leaves at indexes 3 to 6 are never sifted, because the build loop starts at index 2, the last parent, and counts down to 0.
Summary
- A max-heap keeps the largest value at index 0, and each parent is at least as large as its children.
- In a vector, the children of index
iare at2 * i + 1and2 * i + 2. - Sift down moves one value down the heap by swapping it with its larger child until the heap rule holds.
- Heap sort builds the heap from the last parent to the root, then swaps the root with the end and sifts again, which runs in O(n log n) time with O(1) extra space.
- Keep the heap size and the vector size separate, and never sift past the heap size.
- Heap sort is not stable, so use
std::stable_sortwhen equal values must keep their order.