# Week 11 - Heaps

## Team

Team name: Totally Useless
Date: 2022-06-20

Members

| Role | Name |
|-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------|------|
| **Facilitator** keeps track of time, assigns tasks and makes sure all the group members are heard and that decisions are agreed upon. | Adelina |
| **Spokesperson** communicates group’s questions and problems to the teacher and talks to other teams; presents the group’s findings. | Ines |
| **Reflector** observes and assesses the interactions and performance among team members. Provides positive feedback and intervenes with suggestions to improve groups’ processes. | Stefan |
| **Recorder** guides consensus building in the group by recording answers to questions. Collects important information and data. | Tautvydas |

## 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(1) | O(1) | O(n) |
| Sorted linked list | O(1) | O(1) | O(n) |
| Balanced BST | O(height) | O(height) | O(height) |

### Activity 2: Identify valid heaps

Tree 1 and 3 are valid min heap trees because the child nodes of each node are smaller than it.However, tree 2 is not a heap tree because the root value is the max but some child nodes are bigger than the parent nodes.
### Activity 3: Do it yourself

* In order to restore the heap invariant 2 swaps will be performed:
- first step swap 12 and 3
- second step swap 12 and 11

### Activity 4: Worst-case time complexities

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

### Activity 5: Index computations

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

}

size_t maxheap::left_child_index(size_t index) {
    if((2*index)+1 >= m_values.size())
    {
        return maxheap::npos;
    } else
    {
        return (2*index)+1;
    }
}

size_t maxheap::right_child_index(size_t index) {
    if ((2*index)+2>=m_values.size())
    {
        return maxheap::npos;
    }
    else
    {
        return (2*index)+2;
    }
}

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

const task &maxheap::maximum() const {
    return m_values.at(0);
}

### Activity 7: Bubbling up

size_t maxheap::bubble_up(size_t index) {  
size_t swaps = 0;
    if(index==0){
        return swaps;
    }
    while (m_values.at(index) > m_values.at(parent_index(index))) {
            swap(index, parent_index(index));
            index = parent_index(index);
            swaps++;
            if(index==0){
                return swaps;
            }

    }
    return swaps;
}

### Activity 8: Bubbling down

size_t maxheap::bubble_down(size_t index) { 
    size_t swaps = 0;

    while(index != npos) {
        auto left_index = left_child_index(index);
        auto right_index = right_child_index(index);
        auto child_index = right_index == npos ? left_index :
                           (m_values[left_index] > m_values[right_index] ? left_index : right_index);
        if (child_index != npos && m_values[child_index] > m_values[index]) {
            swap(index, child_index);
            swaps++;
            index = child_index;
        } else {
            index = npos;
        }
    }
    return swaps;
}

### Activity 9: Implement heapify

size_t maxheap::heapify() {  
    if (m_values.empty())
    return 0;
size_t swaps = 0;
    int ind_start=(int)this->size();
    while(ind_start>=0) {
        while(right_child_index(ind_start)==maxheap::npos &&
           left_child_index(ind_start)==maxheap::npos){
            ind_start--;
        }
        swaps = swaps + bubble_down(ind_start);
        ind_start--;
    }
    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 |

The time complexity of the function in depended on the depth of the node. If the node is the first one it is O(1) but the worst case time complexity is O(n).

### Activity 11: Bubbling down vector elements

size_t maxheap::bubble_down(size_t index) {
    size_t swaps = 0;

    while(index != npos) {
        auto left_index = left_child_index(index);
        auto right_index = right_child_index(index);
        auto child_index = right_index == npos ? left_index :
                           (m_values[left_index] > m_values[right_index] ? left_index : right_index);
        if (child_index != npos && m_values[child_index] > m_values[index]) {
            swap(index, child_index);
            swaps++;
            index = child_index;
        } else {
            index = npos;
        }
    }
return swaps;
}

size_t maxheap::heapify() {
    if (m_values.empty())
        return 0;
    size_t swaps = 0;
    int ind_start =(int)m_values.size();
    while(ind_start>=0) {
        auto left_child = left_child_index(ind_start);
        auto right_child = right_child_index(ind_start);
        while(left_child == maxheap::npos &&
                right_child == maxheap::npos){
            ind_start--;
            left_child = left_child_index(ind_start);
            right_child = right_child_index(ind_start);
        }
        swaps = swaps + bubble_down(ind_start);
        ind_start--;
    }
    return swaps;
}

### Activity 12: In-place heap sort

void heap_sort(std::vector<int>& values) {  
    heapify(values); 
    while (values.size-- > 1) {
        std::swap (values.at(0), values.size); 
        bubble_down (values, 0, values.size);
    } 
}

### Activity 13: General heap sort

template<typename T>
void heap_sort(T values [], size_t count) {
    heapify(values, count); 
    while (count-- > 1) {
        std::swap (values[0], values[count]); 
        bubble_down (values, 0, count);
    }
}

## Looking back

### What we've learnt

* To explain what a heap is, the structure behind it (with the use of two different data strutures)

### What were the surprises

* Surprising how it is possible to integrate to completely different data structures into one.
*

### What problems we've encountered

* No major difficulties

### How did the group perform?

* Small issues were resolved quickly by having discusions within the group. If there were any larger, more prevalent problems, they were handled by discussing with the teacher.
* As this week's assignment was one of the ones closest to the exam week, the team was eager to communicate so that if any of us have issues or questions, they can be quickly solved. This not only helped us prepare for the exam, but also easily finish the week 11 exercises.