# Week 11 - Heap [Trees]

## Team

Team name: **Group [497441]**
Date: 05/24/2021

Members: Max Thielen

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

## Activities

### Activity 1: Comparing different data structures

Suppose that you would consider the following three data structures for storing a list of prioritized tasks:
* **Sorted array**
* Find Min: O(1)
* Delete Min: O(n)
* Insert: O(n)
* **Sorted linked list**
* Find Min: O(1)
* Delete Min: O(1)
* Insert: O(n)
* **Balanced binary search tree**
* Find Min: O(log(n))
* Delete Min: O(log(n))
* Insert: O(log(n))

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

**Describe how the implementation of a balanced binary search tree can be modified in such a way that the minimum value is always stored inside the root node.**

By having the minimum value of the tree stored in the root node, the order invariant of the binary tree we have learned in the last two weeks gets in our way of keeping the tree efficiently traversible. Since we no longer have a value in the tree that is less than the root there is no left subtree. The only hope of keeping this tree balanced(ish) is to keep the balance in the right subtree.

### Activity 3: Identify valid heaps


The left and right trees are correct both min-heaps. The middle tree attempts disguise itself as a max-heap, however switches into a min-heap from level 2 to 3. All of the level 3 leaf nodes are greater than the two parents on level 2.

### Activity 4: Do it yourself

**In the heap of Figure 2d, suppose that the value 4 is added as a right child of 13. How many, and which specific swaps are needed to restore the heap invariant?**

First 13 would be swapped with 4, placing 13 on the new leaf node and 4 right under 5. But since 4 is still less than its parent (5), another swap happens placing 4 as the right child of 1 and the parent of 19 and 5. In total that is only two swaps to return order to the tree.

### Activity 5: Worst-case time complexities

* **Blanced BTS**
* Find Min: O(log(n))
* Delete Min: O(log(n))
* Insert: O(log(n))
* Find: O(log(n))
* **Binary min-heap**
* Find Min: O(1)
* Delete Min: O(log(n))
* Insert: O(log(n))
* Find: O(n*log(n))

### Activity 6: Moving to arrays

**Suppose that the value 53 is added to the binary heap shown in Figure 4.**
* **At how many positions can you add this new value as a leaf node to the tree without breaking the heap invariant?**

There are four leaf nodes that are less than 53 (29,23,47,17). Therefore, considering that 53 could be placed as either child of all four leaf nodes, there are eight possible placements.
* **At which index would you need to store the new value if you don’t want any gaps in the array’s data? With which position in the tree does your chosen index correspond?**

Index 13 would be the best next index for 53 since index 11 and 12 are reserved for the children of leaf node 87. So adding 53 as the left child of the 17 would leave the least gaps in the array.

### Activity 7: Index computations

int minheap::parent_index(int index) const {
    return index != 0 ? (((index+2)-1) / 2) - 1 : -1;
}

int minheap::left_child_index(int index) const {
    return ((index * 2) + 1<=size()) ? (index * 2) + 1 : -1;
}

int minheap::right_child_index(int index) const {
    return ((index * 2) + 2<=size()) ? (index * 2) + 2 : -1;
}

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

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

### Activity 9: Bubbling up

void minheap::bubble_up(int index) {     
    while(index>0 && m_values[index]<m_values[parent_index(index)]){
        swap(index,parent_index(index));
        index=parent_index(index);
    }
}

### Activity 10: Bubbling down

void minheap::bubble_down(int index) {
    int next_index = 0;
    if((m_values[left_child_index(index)].priority<=m_values[right_child_index(index)].priority||right_child_index(index)<0)&&left_child_index(index)>=0){
        next_index = left_child_index(index);
    }
    else if((m_values[left_child_index(index)].priority>=m_values[right_child_index(index)].priority||left_child_index(index)<0)&&right_child_index(index)>=0){
        next_index = right_child_index(index);
    }
    
    while(m_values[index].priority>m_values[next_index].priority && index<=size()){
        swap(index,next_index);
        index=next_index;
        if(m_values[left_child_index(index)].priority<=m_values[right_child_index(index)].priority&&left_child_index(index)>0){
            next_index = left_child_index(index);
        }
        else if(m_values[left_child_index(index)].priority>=m_values[right_child_index(index)].priority&&right_child_index(index)>0){
            next_index = right_child_index(index);
        }
    }
}

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

### Activity 12: Turning vectors into heaps
Both seem to take O(n) time while bubbling down is slightly more efficient.

### Activity 13: Heaps and sorting
There are repeating prioreties in the m_values array post deletion, since the when replaicing the root value with a a leaf the leaf value is not deleted the array is simply reduced in 'size'.

## Look back

### What we've learnt

About heap trees with new order invarient.

### What were the surprises

Nothing

### What problems we've encountered

None

### What was or still is unclear

Nada

### How did the group perform?

Bueno