---
# System prepended metadata

title: Week 11 - Heaps

---

# Week 11 - Heaps

## Team

Team name:
Date:

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.                                             |      |
| **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
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(n)       |  O(N)      |
| Sorted linked list |    O(1)      |       O(1)     |   O(N)     |
| Balanced BST       |    O(log(n))      |     O(log(n))       |    O(log(n))    |

Record your answer here

### Activity 2: Identify valid heaps
De eerste is een min-heap, de tweede is geen heap en de derde is min-heap


### Activity 3: Do it yourself
twee stappen en hij verwisseld zichzelf met elf en drie


### Activity 4: Worst-case time complexities

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

### Activity 5: Index computations

```c++
size_t maxheap::parent_index(size_t index) {
}

size_t maxheap::left_child_index(size_t index) {
}

size_t maxheap::right_child_index(size_t index) {
}
```

```c=
size_t maxheap::parent_index(size_t index) {
    // Activity 5
    (void) index;
    size_t parent_index = 0;
    if (index % 2 == 0) {
        parent_index =  (index -2)/2;
    }
    else{
        parent_index = (index -1)/2;
    }
    if( parent_index >= size()){
        return npos;
    }
    else{
        return parent_index;
    }

    throw std::logic_error("not implemented");
}

size_t maxheap::left_child_index(size_t index) {
    // Activity 5
    (void) index;
    size_t left_child_index = (index * 2) + 1;
    if( left_child_index >= size()){
        return npos;
    }
    else{
        return left_child_index;
    }
    throw std::logic_error("not implemented");
}

size_t maxheap::right_child_index(size_t index) {
    // Activity 5
    (void) index;
    size_t right_child_index = (index * 2) + 2;
    if(right_child_index >= size()){
        return npos;
    }
    else{
        return right_child_index;
    };
    throw std::logic_error("not implemented");
}
```

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

```c++
const task& maxheap::maximum() const {

}
```

```c=
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
    (void) index;
    size_t swaps = 0;
    while(m_values[parent_index(index)].priority < m_values[index].priority && index != 0){
        swap(parent_index(index), index);
        swaps++;
        index = parent_index(index);
    }
    return swaps;
}
```

### Activity 7: Bubbling up

```c++
size_t maxheap::bubble_up(size_t index) {  
}
```

```c=
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
    (void) index;
    size_t swaps = 0;
    while (m_values[parent_index(index)] < m_values[index] && index != 0) {
        swap(parent_index(index), index);
        swaps++;
        index = parent_index(index);
    }
    return swaps;
}
```

### Activity 8: Bubbling down

```c++
size_t maxheap::bubble_down(size_t index) {  
}
```

```c=
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 values,
    // bubble it down
    // use the functions swap, left_child_index, and right_child_index
    (void) index;
    size_t swaps = 0;
    auto lchild = left_child_index(index);
    auto rchild = right_child_index(index);
    while (lchild != npos) {
        auto maxchild = lchild;    // maxchild is the index of the max. child
        // we have a left child
        // do we have a right child?
        if (rchild != npos && m_values[rchild] > m_values[lchild]) maxchild = rchild;

        if (m_values[maxchild] > m_values[index]) {
            swap(maxchild, index);
            index = maxchild;
            swaps++;
            lchild = left_child_index(index);
            rchild = right_child_index(index);
        }
        else break;
    }
    return swaps;
}
```

### Activity 9: Implement heapify

```c++
size_t maxheap::heapify() {  
}
```
```c=
size_t maxheap::heapify() {
    // Activity 9
    // fix heap violations by bubbling values down, starting with leaf nodes
    size_t swaps = 0;
    for (size_t i = size(); i >= 1; i--) {
        bubble_down(i-1);
        swaps++;
    }
    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        |

o

want in het ergste geval moet je door alle elementen heen.

### Activity 11: Bubbling down vector elements
```c++
void bubble_down(std::vector<int>& values, size_t index, size_t count) {  
}

void heapify(std::vector<int>& values) {  
}
```

````c
while (index*2+1 < count){
    int max = index * 2 + 1;
    if ((index * 2 + 2) < count && values[(index * 2 + 2)] > values[max]){
        max = index*2+2;
    }
    if (values[index] < values[max]){
        std::swap(values[index], values[max]);
        index = max;
    } else {
        break;
    }
}
````

````c
void heapify(std::vector<int> &numbers){
    for (size_t i = (numbers.size()); i > 0; --i) {
        bubble_down(numbers, i - 1, numbers.size());
    }
}
````


### Activity 12: In-place heap sort

```c++
void heap_sort(std::vector<int>& values) {  
}  
```

### Activity 13: General heap sort

Done

## Looking back

### What we've learnt

Formulate at least one lesson learned.

### What were the surprises

Fill in...

### What problems we've encountered

Fill in...

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





