Heap bug hunt

Questions 1 to 5 of 8

1. 1. A pop leaves a heap with 3 items, and the program crashes with the assertion __n < this->size(). This sift_down runs during that pop. What is the bug? ``cpp void sift_down(size_t i) { size_t n = data_.size(); while (true) { size_t left = 2 * i + 1; size_t right = 2 * i + 2; size_t smallest = i; if (left <= n && data_[left] < data_[smallest]) smallest = left; if (right < n && data_[right] < data_[smallest]) smallest = right; if (smallest == i) break; swap(data_[i], data_[smallest]); i = smallest; } } ``

   The right < n check should be right <= nThe left <= n check lets left equal n, so data_[n] is read past the end; it should be left < nThe swap should use std::move, so the item at index 3 is copied safelyThe smallest = i line should start at 1, because the root never needs a check
2. 2. Pushing 5, then 3, then 1 leaves the array as 5 3 1, so the root is not the smallest. What is the bug in this sift_up? ``cpp void sift_up(size_t i) { while (i > 0) { size_t parent = (i - 1) / 2; if (data_[parent] >= data_[i]) break; swap(data_[parent], data_[i]); i = parent; } } ``

   The parent index should be i / 2, not (i - 1) / 2The loop should run while i >= 0, so the root is also checkedThe swap should be replaced with a copy into a temporary vectorThe stop test is reversed: it stops when the parent is larger, and it should stop when the parent is smaller or equal
3. 3. A heap is built from 4, 7 and 6. The program calls set(2, 1) to lower the key of 6 to 1, and then pop() returns 4 instead of 1. Here is set. What is the bug? ``cpp void set(size_t i, int value) { data_[i] = value; } ``

   set writes the new value but never moves the item up, so the 1 sits below its parent 4pop does not check for an empty heap before reading the rootpush should call sift_down, so the 1 would be placed at the rootset takes value by copy, so the change is lost after the call
4. 4. This loop prints a vector, and it compiles with g++ -std=c++20 -Wall. What does the compiler report? ``cpp #include <iostream> #include <vector> int main() { std::vector<int> v{3, 1, 4}; for (int i = 0; i < v.size(); ++i) std::cout << v[i]; std::cout << '\n'; } ``

   An error that stops the build, because a vector cannot be indexed with an intNo problem, because both sides of the comparison are the same sizeA -Wsign-compare warning, because the int i is compared with v.size(), a size_t; use size_t for the indexA crash on the first iteration, because -1 is not a valid vector index
5. 5. What does this program print? ``cpp #include <iostream> #include <vector> using namespace std; int main() { vector<int> v; for (int x : {2, 9, 4}) { v.push_back(x); size_t i = v.size() - 1; while (i > 0) { size_t parent = (i - 1) / 2; if (v[parent] >= v[i]) break; swap(v[parent], v[i]); i = parent; } } for (int x : v) cout << x << ' '; cout << '\n'; } ``

   2 4 92 9 49 2 44 2 9