# Week 11 - Heaps

## Team

Team name: Group
Date: 21-5-2021

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. |Hlib |
| **Spokesperson** communicates group’s questions and problems to the teacher and talks to other teams; presents the group’s findings. |Ijeoma (if mic works) |
| **Reflector** observes and assesses the interactions and performance among team members. Provides positive feedback and intervenes with suggestions to improve groups’ processes. |Cas |
| **Recorder** guides consensus building in the group by recording answers to questions. Collects important information and data. |Yordan |

## Activities

### Activity 1: Comparing different data structures

**What would be the worst-case time complexities for the three required operations, for each of the three data structures?**

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

**Which data structure offers the best performance, and why?**

*Answer: Linked list*

### Activity 2: Storing the minimum value in the root node

**Describe how the implementation of a balanced binary search tree can be modified in such a way that the minimum value is always stored inside the root node.**

*Answer: When inserting a new node, we can compare the new node's value with the root node. If your new node is less than the root, the root node will be inserted in right the right side of the new node, which became the root, otherwise the new node is just inserted in the right side.*

### Activity 3: Identify valid heaps

**Which trees are heaps? For each heap, indicate if it’s a min-heap or a max-heap. For the tree that is not a heap, describe why it is not a heap.**

*Tree 1 = a min-heap.*

*Tree 2 = not a heap because at the left subtree, 1 of the parents is lower than it's children while all the other parents are higher than their children.*

*Tree 3 = a min-heap.*

### Activity 4: Do it yourself

**In the heap of Figure 2d, suppose that the value 4 is added as a right child of 13. How many, and which specific swaps are needed to restore the heap invariant?
**

*Answer; 2 swaps, swap 4 and 13, then 4 and 5.*

### Activity 5: Worst-case time complexities

| Datastructure | Find min | Delete min | Insert| Find|
| -------- | -------- | -------- |-------- |-------- |
|Balanced BST|O(n)|O(n)|O(log2n)|O(log2n)|
|Binary min-heap|O(1)|O(log n)|O(log n)|O(n^2)|

### Activity 6: Moving to arrays

**Suppose that the value 53 is added to the binary heap shown in Figure 4.
• At how many positions can you add this new value as a leaf node to the tree without breaking the heap invariant?**

*Answer: We can insert it at 2 positions: 13,14*

**• At which index would you need to store the new value if you don’t want any gaps in the array’s data? With which position in the tree does your chosen index correspond?
**

*Answer: When inserting into the following indexes, the invariant still holds: 5,6,7,8,9 and 10 all work.*

### Activity 7: Index computations

And that's how you insert code blocks:

Left Child

int minheap::left_child_index(int index) const {
    if (size() <= index*2 + 1){
        return -1;
    }
    return index * 2 + 1;
}

Right Child

int minheap::right_child_index(int index) const {
    if (size() <= index*2 + 2){
        return -1;
    }
    return index * 2 + 2;
}

Parent

int minheap::parent_index(int index) const {
    if (index == 0){
        return -1;
    }
    return (index - 1) / 2;
}

### Activity 8: Implement the find-min operation

const task &minheap::mininum() const {
    return m_values[0];
}

### Activity 9: Bubbling up
##### Code:

void minheap::bubble_up(int index) {
    if (index != 0){
        if (m_values[index] < m_values[parent_index(index)]){
            swap(index, parent_index(index));
            bubble_up(parent_index(index));
        }
    }
}

###### Photo:

### Activity 10: Bubbling down
##### Code:

void minheap::bubble_down(int index) {
    if (left_child_index(index) != -1){
        if (right_child_index(index) == -1){
            if (m_values[index] > m_values[left_child_index(index)]){
                swap(index, left_child_index(index));
                bubble_down(left_child_index(index));
            }
        } else {
            if (m_values[left_child_index(index)] < m_values[right_child_index(index)]) {
                if (m_values[index] > m_values[left_child_index(index)]) {
                    swap(index, left_child_index(index));
                    bubble_down(left_child_index(index));
                }
            } else {
                if (m_values[index] > m_values[right_child_index(index)]) {
                    swap(index, right_child_index(index));
                    bubble_down(right_child_index(index));
                }
            }
        }
    }
}

###### Photo:

### Activity 11: Bottom up - do it yourself

|| i:0 |i:1 | i:2|i:3|i:4|i:5|i:6|
| -------- | -------- | -------- | -------- | -------- | -------- | -------- | -------- |
| Initial array |7|5|6|1|2|3|4|
| After 1 swap |7|5|3|1|2|6|4|
| After 2 swaps |7|1|3|5|2|6|4|
| After 3 swaps |1|7|3|5|2|6|4|
| After 4 swaps |1|2|3|5|7|6|4|

So this takes 4 swaps.

### Activity 12: Turning vectors into heaps

| Number of values|Number of|swaps|
| -------- | -------- | -------- |
||Top-down|Bottom-up |
|5|4|3|
|10|11|8|
|20|27|18|
|50|76|47|
|100|163|97|
|200|338|197|
|500|861|494|
|1000|1754|994|

**• What is the worst-case time complexity when bubbling values up, from top to bottom?**

O(n * 2^n + logn * 2^logn)

**• What is the worst-case time complexity when following the bottom-up approach, bubbling values downwards?**

O(1.5 * n * log n + n)

**• Which of the two strategies does the function std::make_heap in the C++ standard library use?**

Probably it uses bottom-up approach, because it has less time complexity

### Activity 13: Heaps and sorting
CODE:

minheap heap;
        heap << 1 << 4 << 5 << 6 << 2 << 3 << 8 << 2 << 10 << 9 ;
        for (int i = 0; i < heap.size(); ++i) {
            std::cout << heap.values()[i].priority << " ";
        }
        std::cout << std::endl;
        while (heap){
            heap.delete_min();
            for (int i = 0; i < heap.size(); ++i) {
                std::cout << heap.values()[i].priority << " ";
            }
            std::cout << std::endl;
        }

The program deletes the minimum value of the heap on every iteration, until the heap is empty.
### Activity 14: In-place heap sort (optional)

## Look back

### What we've learnt

Fill in...

### What were the surprises

Fill in...

### What problems we've encountered

Fill in...

### What was or still is unclear

Cas: For me, activity 12 (the questions about time complexity) are still unclear :-1:

### How did the group perform?

How was the collaboration? What were the reasons for hick-ups? What worked well? What can be improved next time?