Embercode: AI-powered software engineer course

1. Put the steps of heap sort in the order the algorithm runs them.

Use the arrows to put the steps in order.

1.Sift the new root down in a heap that is one value smaller
2.Repeat the swap and the sift until the heap holds one value
3.Swap the root, which is the largest value, with the last value in the heap
4.Sift down each parent, from the last parent back to the root, to build a max-heap

2. Put the steps of one sift down, starting at index i, in order.

Use the arrows to put the steps in order.

1.Move to the child's index and repeat, or stop if the value did not move
2.Find the largest of the value at index i and its two children, if they are inside the heap
3.If the largest is a child, swap it with the value at index i

3. Predict the output of this program. ``

cpp
#include <cstddef>
#include <iostream>
#include <utility>
#include <vector>

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;
    }
}

int main() {
    std::vector<int> a = {1, 8, 6, 5, 7};
    sift_down(a, 5, 0);
    for (int x : a) std::cout << x << ' ';
    std::cout << '\n';
}

``

8 1 6 5 78 7 6 5 18 7 6 1 58 6 7 5 1

4. Predict the vector after build_max_heap runs on it. ``

cpp
#include <cstddef>
#include <iostream>
#include <utility>
#include <vector>

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 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);
    }
}

int main() {
    std::vector<int> a = {1, 2, 3, 4, 5, 6, 7};
    build_max_heap(a);
    for (int x : a) std::cout << x << ' ';
    std::cout << '\n';
}

``

7 5 6 4 2 3 17 6 5 4 2 1 31 5 7 4 2 6 37 5 6 4 2 1 3

5. Heap sort runs on n values in a random order. What is its running time in the best, average and worst cases?

O(n^2) in the worst case and O(n log n) on averageO(n) in the best case and O(n log n) in the worst caseO(n log n) in every caseO(n^2) in every case