# Week 11 - Heaps

## Team

Team name: Gappies van andere wappies
Date: 16/6/2022

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. |Steohan|
| **Spokesperson** communicates group’s questions and problems to the teacher and talks to other teams; presents the group’s findings. |Ingmar|
| **Reflector** observes and assesses the interactions and performance among team members. Provides positive feedback and intervenes with suggestions to improve groups’ processes. |Ingmar|
| **Recorder** guides consensus building in the group by recording answers to questions. Collects important information and data. |Stijn|

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

Best: Sorted array/ sorted linked list

### Activity 2: Identify valid heaps ✅

1st tree: Min-heap
2nd tree: Not a heap. Because if you look at the path from the root to the bottom left node, it is not sorted. So the heap invariant does not hold true.
3rd tree: Min-heap

### Activity 3: Do it yourself ✅

1st swap: 12 - 3
2nd swap: 12 - 11

After these two swaps, the parent value is higher than 12 so the path is not sorted again. This took 2 swaps.

### Activity 4: Worst-case time complexities ✅

| Data structure | Find-max | Delete-Max | Insert | Find |
|-----------------|:--------:|:----------:|:------:|:----:|
| Balanced BST | O(log n) | 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) {
    // Activity 5
    return floor(((double)index - 1) / 2);
}

size_t maxheap::left_child_index(size_t index) {
    // Activity 5
    size_t left_child = index * 2 + 1;
    if(left_child > size() - 1) {
        return npos;
    }

    return left_child;
}

size_t maxheap::right_child_index(size_t index) {
    // Activity 5
    size_t right_child = index * 2 + 2;
    if(right_child > size() - 1) {
        return npos;
    }

    return right_child;
}

Executing this code outputs:

test_left_child_index PASS
test_right_child_index PASS
test_parent_index PASS

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

const task &maxheap::maximum() const {
    // Activity 6
    return m_values[0];
}

The max value is simply the first index.

### Activity 7: Bubbling up ✅

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
    // using the functions swap and parent_index

    size_t swaps = 0;
    size_t p_index;
    int priority;
    int parent_priority;

    do {
        p_index = parent_index(index);

        // Make sure there is a parent node.
        if(p_index != npos) {
            priority = m_values[index].priority;
            parent_priority = m_values[p_index].priority;

            if(priority > parent_priority) {
                swap(index, p_index);
                swaps += 1;

                // Swap indices
                index = p_index;
            }
        }
    } while(priority > parent_priority && p_index != npos);

    return swaps;
}

### Activity 8: Bubbling down ✅

size_t maxheap::bubble_down(size_t index) {
    size_t swaps = 0;
    auto currentIndex = index;
    auto leftChildIndex = left_child_index(currentIndex);
    auto rightChildIndex = right_child_index(currentIndex);
    while (m_values[currentIndex] <  m_values[leftChildIndex] || m_values[currentIndex] < m_values[rightChildIndex]) {
        if (std::max(m_values[leftChildIndex].priority, m_values[rightChildIndex].priority) == m_values[leftChildIndex].priority) {
            swap(currentIndex, left_child_index(currentIndex));
            swaps++;
            currentIndex = left_child_index(currentIndex);
            leftChildIndex = left_child_index(currentIndex);
            rightChildIndex = right_child_index(currentIndex);
            continue;
        } else {
            swap(currentIndex, right_child_index(currentIndex));
            swaps++;
            currentIndex = right_child_index(currentIndex);
            leftChildIndex = left_child_index(currentIndex);
            rightChildIndex = right_child_index(currentIndex);
        }
    }
    return swaps;
}

### Activity 9: Implement heapify ✅

size_t maxheap::heapify() {
    size_t swaps = 0;
    if (!this->m_values.empty()) {
        swaps = heapifyTree(0);
    }
    return swaps;
}

size_t maxheap::heapifyTree(size_t index) {
    size_t swaps{0};
    auto biggestIndex = index;
    auto leftChildIndex = left_child_index(index);
    auto rightChildIndex = right_child_index(index);

    if (!invariantHolds(leftChildIndex)) {
        swaps += heapifyTree(leftChildIndex);
    }
    if (!invariantHolds(rightChildIndex)) {
        swaps +=heapifyTree(rightChildIndex);
    }

    if (leftChildIndex != npos && this->m_values[leftChildIndex] > this->m_values[biggestIndex]) {
        biggestIndex = leftChildIndex;
    } else if (rightChildIndex != npos && this->m_values[rightChildIndex] > this->m_values[biggestIndex]) {
        biggestIndex = rightChildIndex;
    }
    if (biggestIndex != index) {
        swaps += bubble_down(index);
    }

    return swaps;
}

bool maxheap::invariantHolds (size_t i) {
    auto leftChildIndex = left_child_index(i);
    auto rightChildIndex = right_child_index(i);
    if (i == npos) {
        return true;
    }
    if (leftChildIndex != npos && m_values[leftChildIndex] > m_values[i]) {
        return false;
    } else if (rightChildIndex != npos && m_values[rightChildIndex] > m_values[i]) {
        return false;
    }
    return true;
}

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

As you can see the number of swaps is almost exactly the number of values, so the worst case time complexity is O(n)

### Activity 11: Bubbling down vector elements ✅

size_t left_child_index(std::vector<int> &numbers, size_t index) {
    size_t left_child = index * 2 + 1;
    if(left_child > numbers.size() - 1) {
        return std::string::npos;
    }

    return left_child;
}

size_t right_child_index(std::vector<int> &numbers, size_t index) {
    size_t right_child = index * 2 + 2;
    if(right_child > numbers.size() - 1) {
        return std::string::npos;
    }

    return right_child;
}

void swap(std::vector<int> &numbers, size_t first_index, size_t second_index) {
    std::swap(numbers[first_index], numbers[second_index]);
}

void bubble_down(std::vector<int> &values, size_t index, size_t count) {
    auto currentIndex = index;
    auto leftChildIndex = left_child_index(values, currentIndex);
    auto rightChildIndex = right_child_index(values, currentIndex);
    while ((values[currentIndex] <  values[leftChildIndex] || values[currentIndex] < values[rightChildIndex])) {
        if (leftChildIndex >= count) break;
        if (std::max(values[leftChildIndex], values[rightChildIndex]) == values[leftChildIndex]
        || rightChildIndex == count
        || rightChildIndex == std::string::npos) {
            if (leftChildIndex == std::string::npos) break;
            swap(values, currentIndex, left_child_index(values, currentIndex));
            currentIndex = left_child_index(values, currentIndex);
            leftChildIndex = left_child_index(values, currentIndex);
            rightChildIndex = right_child_index(values, currentIndex);
            continue;
        } else {
            if (rightChildIndex == std::string::npos) break;
            swap(values, currentIndex, right_child_index(values, currentIndex));
            currentIndex = right_child_index(values, currentIndex);
            leftChildIndex = left_child_index(values, currentIndex);
            rightChildIndex = right_child_index(values, currentIndex);
        }
    }
}

bool invariantHolds (std::vector<int> &numbers, size_t i) {
    auto leftChildIndex = left_child_index(numbers,i);
    auto rightChildIndex = right_child_index(numbers, i);
    if (i == std::string::npos) {
        return true;
    }
    if (leftChildIndex != std::string::npos && numbers[leftChildIndex] > numbers[i]) {
        return false;
    } else if (rightChildIndex != std::string::npos && numbers[rightChildIndex] > numbers[i]) {
        return false;
    }
    return true;
}

void heapifyTree(std::vector<int> &numbers, size_t index) {
    auto biggestIndex = index;
    auto leftChildIndex = left_child_index(numbers, index);
    auto rightChildIndex = right_child_index(numbers, index);

    if (!invariantHolds(numbers, leftChildIndex)) {
        heapifyTree(numbers, leftChildIndex);
    }
    if (!invariantHolds(numbers, rightChildIndex)) {
        heapifyTree(numbers, rightChildIndex);
    }

    if (leftChildIndex != std::string::npos && numbers[leftChildIndex] > numbers[biggestIndex]) {
        biggestIndex = leftChildIndex;
    } else if (rightChildIndex != std::string::npos && numbers[rightChildIndex] > numbers[biggestIndex]) {
        biggestIndex = rightChildIndex;
    }
    if (biggestIndex != index && index < numbers.size()) {
        bubble_down(numbers, index, numbers.size());
    }
}

// Activity 11
void heapify(std::vector<int> &numbers) {
    if (!numbers.empty()) {
        heapifyTree(numbers, 0);
    }
}

### Activity 12: In-place heap sort ✅

void heap_sort(std::vector<int> &numbers) {
    heapify(numbers);
    auto end = numbers.size() - 1;
    while (end > 0) {
        if (numbers[0] > numbers[end]) std::swap(numbers[0], numbers[end]);
        end--;
        bubble_down(numbers, 0, end);
    }
}

### Activity 13: General heap sort ✅

template <typename T>
size_t left_child_index(std::vector<T> &numbers, size_t index) {
    size_t left_child = index * 2 + 1;
    if(left_child > numbers.size() - 1) {
        return std::string::npos;
    }

    return left_child;
}

template <typename T>
size_t right_child_index(std::vector<T> &numbers, size_t index) {
    size_t right_child = index * 2 + 2;
    if(right_child > numbers.size() - 1) {
        return std::string::npos;
    }

    return right_child;
}

template <typename T>
void swap(std::vector<T> &numbers, size_t first_index, size_t second_index) {
    std::swap(numbers[first_index], numbers[second_index]);
}

template <typename T>
void bubble_down(std::vector<T> &values, size_t index, size_t count) {
    auto currentIndex = index;
    auto leftChildIndex = left_child_index(values, currentIndex);
    auto rightChildIndex = right_child_index(values, currentIndex);
    while ((values[currentIndex] <  values[leftChildIndex] || values[currentIndex] < values[rightChildIndex])) {
        if (leftChildIndex >= count) break;
        if (std::max(values[leftChildIndex], values[rightChildIndex]) == values[leftChildIndex]
        || rightChildIndex == count
        || rightChildIndex == std::string::npos) {
            if (leftChildIndex == std::string::npos) break;
            swap(values, currentIndex, left_child_index(values, currentIndex));
            currentIndex = left_child_index(values, currentIndex);
            leftChildIndex = left_child_index(values, currentIndex);
            rightChildIndex = right_child_index(values, currentIndex);
            continue;
        } else {
            if (rightChildIndex == std::string::npos) break;
            swap(values, currentIndex, right_child_index(values, currentIndex));
            currentIndex = right_child_index(values, currentIndex);
            leftChildIndex = left_child_index(values, currentIndex);
            rightChildIndex = right_child_index(values, currentIndex);
        }
    }
}

template <typename T>
bool invariantHolds (std::vector<T> &numbers, size_t i) {
    auto leftChildIndex = left_child_index(numbers,i);
    auto rightChildIndex = right_child_index(numbers, i);
    if (i == std::string::npos) {
        return true;
    }
    if (leftChildIndex != std::string::npos && numbers[leftChildIndex] > numbers[i]) {
        return false;
    } else if (rightChildIndex != std::string::npos && numbers[rightChildIndex] > numbers[i]) {
        return false;
    }
    return true;
}

template <typename T>
void heapifyTree(std::vector<T> &numbers, size_t index) {
    auto biggestIndex = index;
    auto leftChildIndex = left_child_index(numbers, index);
    auto rightChildIndex = right_child_index(numbers, index);

    if (!invariantHolds(numbers, leftChildIndex)) {
        heapifyTree(numbers, leftChildIndex);
    }
    if (!invariantHolds(numbers, rightChildIndex)) {
        heapifyTree(numbers, rightChildIndex);
    }

    if (leftChildIndex != std::string::npos && numbers[leftChildIndex] > numbers[biggestIndex]) {
        biggestIndex = leftChildIndex;
    } else if (rightChildIndex != std::string::npos && numbers[rightChildIndex] > numbers[biggestIndex]) {
        biggestIndex = rightChildIndex;
    }
    if (biggestIndex != index && index < numbers.size()) {
        bubble_down(numbers, index, numbers.size());
    }
}

template <typename T>
void heapify(std::vector<T> &numbers) {
    if (!numbers.empty()) {
        heapifyTree(numbers, 0);
    }
}

template <typename T>
void heap_sort(std::vector<T> &numbers) {
    heapify(numbers);
    auto end = numbers.size() - 1;
    while (end > 0) {
        if (numbers[0] > numbers[end]) std::swap(numbers[0], numbers[end]);
        end--;
        bubble_down(numbers, 0, end);
    }
}

## Looking back

### What we've learnt

Which heaps there were, and the advantages of each of them.

### What were the surprises

That heaps could be used in different ways.

### What problems we've encountered

There were no big problems that we encountered.

### What was or still is unclear

Nothing, the things we didn't know we asked in class.

### How did the group perform?

Very well as always. :)