# Week 11 - Heaps

## Team

Team name: Academy Award Winning, Choccy Milk Drinking, Argonian Maid Reading, Chair-men, Cross Dressing SIMPS In Yugoslavia With Honda Accords On The Quest For Feet

Date: 23/05/2022
yes(66%)

Members
Mihnea: Mihnea Bastea (514541)
Vlad: Vladislav Serafimov (509761)
Steve: Stephen Cruz Wright (521476)

| Role | Name |
| ------------------------------------------------------------------------------------------------------------------------------------- | ------ |
| **Facilitator** keeps track of time, assigns tasks and makes sure all the group members are heard and that decisions are agreed upon. | Steve |
| **Spokesperson** communicates group’s questions and problems to the teacher and talks to other teams; presents the group’s findings. | Mihnea |
| **Recorder** guides consensus building in the group by recording answers to questions. Collects important information and data. | Vlad |

## Activities
Make sure to have the activities signed off regularly to ensure progress is tracked.

Download the provided project and open it in CLion. **NOTE**: in this week you will have to reuse the code of last week. Follow the instructions given in the `main.cpp` file.

### Activity 1: Comparing different data structures

| Data structure | Find-max | Delete-Max | Insert |
| ------------------ |:---------:|:----------:| --------- |
| Sorted array | O(log(n) | O(n) | O(1) |
| Sorted linked list | O(n) | O(1) | O(1) |
| Balanced BST | O(log(n)) | O(log(n)) | O(log(n)) |

### Activity 2: Identify valid heaps

The left tree is a min-heap.
The middle tree is not a heap because 29 is smaller than both 37 and 31, makin it not the maximum.
the right tree is a min-heap.

### Activity 3: Do it yourself

Swapped 12 and 3.
Swapped 12 and 11.

so just 2 swaps

### Activity 4: Worst-case time complexities

| Data structure | Find-max | Delete-Max | Insert | Find |
| --------------- |:--------:|:----------:|:---------:|:---------:|
| Balanced BST | O(n) | O(n) | O(log(n)) | O(log(n)) |
| Binary max-heap | O(1) | O(log(n)) | O(n) | O(n) |

### Activity 5: Index computations

size_t maxheap::parent_index(size_t index) {
    // Activity 5
    auto idx = (index - 1) / 2;
    if (index == 0) return npos;
    else return idx;
}

size_t maxheap::left_child_index(size_t index) {
    // Activity 5
    auto idx = 2 * index + 1;
    if (m_values[idx].priority == 0) return npos;
    else return idx;
}

size_t maxheap::right_child_index(size_t index) {
    // Activity 5
    auto idx = 2 * index + 2;
    if (m_values[idx].priority == 0) return npos;
    else return idx;
}

### Activity 6: Implement the find-max operation

const task &maxheap::maximum() const {
    // Activity 6
    return m_values[0];
}

### Activity 7: Bubbling up

size_t maxheap::bubble_up(size_t index) {
    // Activity 7
    // while the value at the given index is greater than its parent value,
    // bubble it up
    // use the functions swap and parent_index
    int Count = 0;
    while (index > 0 && m_values[parent_index(index)].priority <= m_values[index].priority) {
        swap(parent_index(index), index);
        index = parent_index(index);
        ++Count;
    }
    return Count;
}

### Activity 8: Bubbling down

size_t maxheap::bubble_down(size_t index) {
    // Activity 8
    // While the value at the given index is smaller than any of its two child m_values,
    // bubble it down
    // use the functions swap, left_child_index, and right_child_index
    int Count = 0;
    size_t child = left_child_index(index);
    while (child < size()) {
        if (right_child_index(index) < size() && m_values[right_child_index(index)].priority > m_values[left_child_index(index)].priority) child++;
        if (m_values[child].priority <= m_values[index].priority) return Count;
        swap(child, index);
        index = child;
        child = left_child_index(index);
        ++Count;
    }
    return Count;
}

### Activity 9: Implement heapify

size_t maxheap::heapify() {
    // Activity 9
    // fix heap violations by bubbling m_values down, starting with leaf nodes
    size_t swaps = 0;
    for (auto i = size(); i > 1; --i) {
        swaps+=bubble_down((i-1)/2);
    }
    return swaps;
}

### Activity 10: Heapify - time complexity

| Number of values | Number of swaps |
| ---------------- |:---------------:|
| 5 | 3 |
| 10 | 8 |
| 20 | 17 |
| 50 | 47 |
| 100 | 96 |
| 200 | 195 |
| 300 | 295 |
| 400 | 394 |
| 500 | 493 |
| 1000 | 992 |

it is O(n) as it need to swap about the same times as the number of values

### Activity 11: Bubbling down vector elements

void bubble_down(std::vector<int> &values, size_t index, size_t count) {
    auto child = 2 * index + 1;
    while (child < count) {
        if (child + 1 < count &&
            values[child + 1] > values[child]) child++;
        if (values[child] <= values[index]) return;
        std::swap(values[child], values[index]);
        index = child;
        child = 2 * index + 1;
    }
}

void heapify(std::vector<int> &numbers){
    for (auto i = numbers.size(); i > 1; --i) {
        bubble_down(numbers,(i-1)/2 , numbers.size());
    }
}

### Activity 12: In-place heap sort

void heap_sort(std::vector<int> &numbers) {
    heapify(numbers);
    auto count = numbers.size();
    while (count-- > 1) {
        std::swap(numbers[count], numbers[0]);
        bubble_down(numbers, 0, count);
    }
}

### Activity 13: General heap sort

template<typename T>
void bubble_down(std::vector<T> &values, size_t index, size_t count) {
    auto child = 2 * index + 1;
    while (child < count) {
        if (child + 1 < count &&
            values[child + 1] > values[child])
            child++;
        if (values[child] <= values[index]) return;
        std::swap(values[child], values[index]);
        index = child;
        child = 2 * index + 1;
    }
}

template<typename T>
void heapify(std::vector<T> &numbers) {
    for (auto i = numbers.size(); i > 1; --i) {
        bubble_down(numbers, (i - 1) / 2, numbers.size());
    }
}

template<typename T>
void heap_sort(std::vector<T> &numbers) {
    heapify(numbers);
    auto count = numbers.size();
    while (count-- > 1) {
        std::swap(numbers[count], numbers[0]);
        bubble_down(numbers, 0, count);
    }
}

The program ran without any errors

## Looking back

### What we've learnt

The ins and outs of heaps as well as the fact that theyre only really useful for quickly finding the max or min values.

### What were the surprises

how difficult it was to implement binary heaps

### What problems we've encountered

Converting the visualisation of the heaps to code

### What was or still is unclear

nothing

### How did the group perform?

well