# 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 | 1 | 1 | O(n) |
| Sorted linked list | O(n) | O(n) | O(n) |
| Balanced BST | 1 | 1 | O(n) |

Record your answer here

### Activity 2: Identify valid heaps

1: is a min-heap
2: is a max-heap
3: is not a heap, because a heap is a complete balanced binary tree

### Activity 3: Do it yourself

Record your answer here

### Activity 4: Worst-case time complexities

| Data structure | Find-max | Delete-Max | Insert | Find |
|-----------------|:--------:|:----------:|:------:|:----:|
| Balanced BST | O(log2n)| O(log2n) |O(log2n)| O(log2n) |
| Binary max-heap | 1 | 1 |O(log2n)|O(log2n)|

### Activity 5: Index computations

size_t maxheap::parent_index(size_t index) {
    // Activity 5
    (void) index;
    if(index == 0)
        return -1;

    return (index - 1) / 2;
}

size_t maxheap::left_child_index(size_t index) {
    // Activity 5
    (void) index;
    if(index < size())
        return ((2*index) + 1);
    else
        return -1;
}

size_t maxheap::right_child_index(size_t index) {
    // Activity 5
    (void) index;
    if(index < size())

        return ((2*index) + 2);
    else
        return -1;
}

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

const task& maxheap::maximum() const {

}

### Activity 7: Bubbling up

size_t maxheap::bubble_up(size_t index) {  
}

### Activity 8: Bubbling down

size_t maxheap::bubble_down(size_t index) {  
}

### Activity 9: Implement heapify

size_t maxheap::heapify() {  
}

### Activity 10: Heapify - time complexity

| Number of values | Number of swaps |
|------------------|:----------------:|
| 5 | 3 |
| 10 | |
| 20 | |
| 50 | |
| 100 | |
| 200 | |
| 300 | |
| 400 | |
| 500 | |
| 1000 | |

Record your answer here

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

### Activity 12: In-place heap sort

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

### Activity 13: General heap sort

Record your answer here

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