---
# System prepended metadata

title: Week 11 - Heaps

---

# Week 11 - Heaps

## Team

Team name Group 2
Date: 21/5/2021

Members: Zahir Josefina
         Len Bauer
         Sebastian Wojciechowski

| Role                                                                                                                                                                          | Name |
|-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------|------|
| **Facilitator** keeps track of time, assigns tasks and makes sure all the group members are heard and that decisions are agreed upon.                                             |Zahir Josefina      |
| **Spokesperson** communicates group’s questions and problems to the teacher and talks to other teams; presents the group’s findings.                                              |Len Bauer|
| **Reflector** observes and assesses the interactions and performance among team members. Provides positive feedback and intervenes with suggestions to improve groups’ processes. | Zahir Josefina     |

| **Recorder** guides consensus building in the group by recording answers to questions. Collects important information and data.                                                   |  Sebastian Wojciechowski    |

## Activities

### Activity 1: Comparing different data structures

| Data Srtuctures   | Find-min | Delete-min     | Insert   |
|---				|	---	   |---				|  --	   |
|Sorted arrays      | O(1)     | O(1)           | O(log n) |
|Sorted linked list | O(1)     | O(1)           | O(n)     |
|Balanced BST       | O(logn)  | O(logn)        | O(logn)  |


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

The implementation of a balanced binary tree would rotate right untill the left child node of the root node will be empty ( nullptr ). This approach however, most likely won't keep the tree balanced.

### Activity 3: Identify valid heaps


Both 1 and 3 are valid min-heaps.
The second tree on the other hand does not follow the heap invariant 
child nodes of node 29 and node 37 should be lower to keep that invariant.


### Activity 4: Do it yourself

Step 1: attaching value of 4 to the right of 13
Step 2: swapping values 4 and 13
Step 3: swapping value 4 and 5

### Activity 5: Worst-case time complexities



| Data Structure    | Find-min | Delete-min | Insert  | Find    |
| --------          | -------- | --------   | --      |  --     |
| Balanced BST      | O(log n) | O(log n)   | O(log n)| O(log n)|
| Binary min-heap   | O(1)     | Θ(log n)   | O(log n)| O(n)    | 

### Activity 6: Moving to arrays

If we count left leaf and right leaf as different positions then we can add 53 at 8 positions (under nodes 29, 23, 47 and 17). 

If we don't want to have any gaps in the array's data we should insert it at index 11 which would be the left leaf of node 87. This foces us to swap the values to keep the invariant.

### Activity 7: Index computations

And that's how you insert code blocks:

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

}

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

int minheap::right_child_index(int index) const {

    if ((2 * index + 2) < (int) m_size)
    {
        return (2*index + 2);
    }
    return -1;
}
```

### Activity 8: Implement the find-min operation
```c=
    const task &minheap::mininum() const {
    return m_values[0];
}
```
### Activity 9: Bubbling up
```c=
void minheap::bubble_up(int index) {
    int parentIdx = parent_index(index);
    int currentIdx = index;
    while (currentIdx > 0 && m_values[parentIdx] > m_values[currentIdx]) {

        swap(currentIdx,parentIdx);
        currentIdx = parentIdx;
        parentIdx = parentIdx/2;
    }
}
```
### Activity 10: Bubbling down
```c=
void minheap::bubble_down(int index) {
    int childLeft = left_child_index(index);
    int childRight = right_child_index(index);
    if (childLeft >= 0 && childRight >= 0 && m_values[childLeft] > m_values[childRight]) {
       swap(childLeft, childRight);
    }
    if (childLeft > 0 && m_values[index] > m_values[childLeft]) {
        task temp = m_values[index];
        m_values[index] = m_values[childLeft];
        m_values[childLeft] = temp;
        bubble_down(childLeft);
    }
}
```
### 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?

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

### Activity 13: Heaps and sorting
CODE:
```c=
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;
        }
```

### Activity 14: In-place heap sort (optional)

## Look back

### What we've learnt

This week we learned of binary Heap and how to implement it. 

### What were the surprises

There weren't many surprises this week maybe how more effecient the heap appears to be compared to the normal binary tree. 

### What problems we've encountered

We didn't encounter many problems related to the activities. 

### What was or still is unclear

Theory wise everything is clear. 

### 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?

The Collabration of the group was pretty good , we had some diffuculty meeting up after the first meeting due to Project
System but aside from that the perfermance was good. 

