# 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

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) {
}

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

const task& maxheap::maximum() const {

}

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

size_t maxheap::bubble_up(size_t index) {  
}

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

size_t maxheap::bubble_down(size_t index) {  
}

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

size_t maxheap::heapify() {  
}

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

void bubble_down(std::vector<int>& values, size_t index, size_t count) {  
}

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

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;
    }
}

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

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?