---
# System prepended metadata

title: Week 11 - Heaps

---

# Week 11 - Heaps

## Team

Team name:
Date: 21-05-2021

Members:
Anton Vorderman
Nian Luisman
Thom Kistemaker

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

## Activities

### Activity 1: Comparing different data structures

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

Best performance depends on what you need. But in general its the balanced BST

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

Zodra er een waarde in komt zet je die bovenaan. De tweede waarde, zolang die groter is, zet je die ergens er onder. Dit doe je steeds verder op dezelfde manier als je een BST opbouwt. Zodra de waarde kleiner is dan de vorige waarde, vervang je de oude waarde met de nieuwe waarde en ga je verder om de oude waarde op de goeie plek te zetten.

### Activity 3: Identify valid heaps

Links en rechts zijn min-heaps. De middelste is incorrect. Het zou een max-heap moeten zijn maar de onderste 4 getallen zijn groter dan hun parents ipv kleiner.

### Activity 4: Do it yourself

First: Swap 13 and 4.
Second: Swap 5 and 4.
Dus 2 swaps

### Activity 5: Worst-case time complexities

|Data Structure       | Find-min | Delete-min  | Insert |find  |
|---------------------|-----------|------------|--------|------|
|Balanced BST         | O(h)      | O(h)       | O(h)   |O(h)  |
|Binary min-heap      | O(1)      | O(h)       | O(h)   |O(n^2)|
### Activity 6: Moving to arrays

Only under the number 17 (indexes 13 & 14)

Je kunt niet zonder de array te veranderen deze waarde, zonder een gat in de array te creëren, ergens plaatsen.
Ik zou hem op index 5 plaatsen en 87 dan verplaatsen naar index 11

### Activity 7: Index computations

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

int minheap::left_child_index(int index) const {
    if (index*2+1 >= (int)this->m_size){
        return -1;
    }
    else{
        return index*2+1;
    }
}

int minheap::right_child_index(int index) const {
    if(index*2+2 >= (int)this->m_size){
        return -1;
    }
    else{
        return index*2+2;
    }
}
```

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

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

### Activity 9: Bubbling up

```cpp=
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));
        }
    }
}
```

### Activity 10: Bubbling down

```cpp=
void minheap::bubble_down(int index) {
    if((index*2)+2 < (int)m_size) {
        if (m_values[index] > m_values[left_child_index(index)] && m_values[left_child_index(index)] < m_values[right_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));
        }
    }
}
```

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

| Initial Array | 7 | 5 | 6 | 1 | 2 | 3 | 4 |               |
|---------------|---|---|---|---|---|---|---|---------------|
| After 1 swap  | 7 | 5 | 3 | 1 | 2 | 6 | 4 | Swapped 3 & 6 |
| After 2 swaps | 7 | 1 | 3 | 5 | 2 | 6 | 4 | Swapped 1 & 5 |
| After 3 swaps | 1 | 7 | 3 | 5 | 2 | 6 | 4 | Swapped 1 & 7 |
| After 4 swaps | 1 | 2 | 3 | 5 | 7 | 6 | 4 | Swapped 2 & 7 |

### Activity 12: Turning vectors into heaps

| Number of values | Swaps Bubbling Up | Swaps Bubbling Down |
|------------------|-------------------|---------------------|
|5                 |4                  |3                    |
|10                |11                 |7                    |
|20                |27                 |16                   |
|50                |76                 |46                   |
|100               |163                |95                   |
|500               |861                |492                  |
|1000              |1754               |991                  |

1. O(n Log n)
2. O(N)
3. Bottom-up

### Activity 13: Heaps and sorting

```cpp=
    minheap heap = generate_vector(10);
    while(heap.size() > 0){
        heap.delete_min();
    }
    for (int i = 0; i < 10; i++){
        std::cout << heap.values()[i].priority << " - " << heap.values()[i].description << std::endl;
    }
```

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

## Look back

### What we've learnt

Fill in...

### What were the surprises

t/m activity 5 was super simpel.

### What problems we've encountered

Activity 6: Beetje verwarrende vraag. Weet niet zo goed wat nou de bedoeling is.
Activity 7: We liepen hier lange tijd vast
Activity 10: Er wordt geen correct word bestand gegenerate voor de website http://graphviz.it/
Activity 12: staat dat in main.cpp de functie generate_tasks staat maar daar staat alleen generate_vector
Activity 13: Geen duidelijke conclusie uit kunnen halen

### What was or still is unclear

Fill in...

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