# Week 11 - Heaps
## Team
Team name:Error
Date: 25/05/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. |Thanh 516467 |
| **Spokesperson** communicates group’s questions and problems to the teacher and talks to other teams; presents the group’s findings. |Minh 511907 |
| **Reflector** observes and assesses the interactions and performance among team members. Provides positive feedback and intervenes with suggestions to improve groups’ processes. | Kaloyan 511216 |
| **Recorder** guides consensus building in the group by recording answers to questions. Collects important information and data. |Hoa 487272 |
## 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(n) |O(n) |O(n) |
| Balanced BST |O(logn) |O(logn) |O(logn) |
Each of these data structure has pros and cons so it depends on what kind of thing we are working on to choose the suitable solutions
### Activity 2: Identify valid heaps
The first graph is a min-heap
The second graph is not a heap because the tree is not as left as it should be
The third graph is not a heap because the tree is not complete and not as left as it should be
### Activity 3: Do it yourself
Swap 12 to 3 then swap 12 to 11
### Activity 4: Worst-case time complexities
| Data structure | Find-max | Delete-Max | Insert | Find |
|-----------------|:--------:|:----------:|:------:|:----:|
| Balanced BST | O(logn) | O(logn) | O(logn)| O(logn)|
| Binary max-heap | O(1) | O(logn) | O(logn)| O(n) |
### Activity 5: Index computations
```c++
size_t maxheap::parent_index(size_t index) {
// Activity 5
(void) index;
if(index>0){
if(index%2==0){
return index/2-1;
}
else{
return index/2;
}
}else{
return npos;
}
}
size_t maxheap::left_child_index(size_t index) {
// Activity 5
(void) index;
return (2*index+1)>=m_values.size()?npos:(2*index+1);
}
size_t maxheap::right_child_index(size_t index) {
// Activity 5
(void) index;
return (2*index+2)>=m_values.size()?npos:(2*index+2);
}
```
### Activity 6: Implement the find-max operation
```c++
const task &maxheap::maximum() const {
// Activity 6
return m_values[0];
}
```
### Activity 7: Bubbling up
```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;
auto check= parent_index(index);
while(check!=npos){
if(m_values[check].priority<m_values[index].priority){
swap(parent_index(index),index);
swaps++;
index=check;
check= parent_index(check);
}else{
break;
}
}
return swaps;
}
```
### Activity 8: Bubbling down
```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
size_t swaps = 0;
auto check_left = left_child_index(index);
auto check_right = right_child_index(index);
while (check_right != npos && check_left != npos) {
if (m_values[index].priority < m_values[check_left].priority &&
m_values[check_right].priority <= m_values[check_left].priority) {
swap(left_child_index(index), index);
++swaps;
index = check_left;
check_left = left_child_index(check_left);
check_right = right_child_index(check_right);
} else if (m_values[index].priority < m_values[check_right].priority &&
m_values[check_left].priority <= m_values[check_right].priority) {
swap(right_child_index(index), index);
++swaps;
index = check_right;
check_right = right_child_index(check_left);
check_left = left_child_index(check_left);
} else break;
}
if (check_left != npos && m_values[check_left].priority >= m_values[index].priority) {
++swaps;
swap(check_left, index);
} else if (check_right != npos && m_values[check_right].priority >= m_values[index].priority) {
++swaps;
swap(check_right, index);
}
return swaps;
}
```
### Activity 9: Implement heapify
```c++
size_t maxheap::heapify() {
// Activity 9
// fix heap violations by bubbling values down, starting with leaf nodes
size_t swaps = 0;
for (int i = (int)m_values.size() / 2 - 1; i >= 0; i--) {
swaps += bubble_down(i);
}
return swaps;
}
```
### Activity 10: Heapify - time complexity
| Number of values | Number of swaps |
|------------------|:----------------:|
| 5 | 3 |
| 10 | 8 |
| 20 | 17 |
| 50 | 40 |
| 100 | 80 |
| 200 | 158 |
| 300 | 239 |
| 400 | 310 |
| 500 | 377 |
| 1000 | 754 |
```c
bool heap_tester::test_heapify() {
maxheap heap{};
for (int prio = 1; prio <= 10; ++prio) {
heap.m_values.push_back({prio, "dummy"});
}
/////////////////std::cout<<heap.heapify()<<std::endl;
auto swapcount = heap.heapify();
assert(8 == swapcount);
```
For this activity just add the cout after the for loop in the heapify test function and it will print the number of swaps. And of course change the number of upper limit of the for loop according to the values we want to see.
### Activity 11: Bubbling down vector elements
```c++
// Activity 11
void bubble_down(std::vector<int> &values, size_t index, size_t count){
auto largest = index;
auto l = 2 * index + 1;
auto r = 2 * index + 2;
if (l < count && values[l] > values[largest])
largest = l;
if (r < count && values[r] > values[largest])
largest = r;
if (largest != index) {
std::swap(values[index], values[largest]);
bubble_down(values, largest, count);
}
};
// Activity 11
void heapify(std::vector<int> &numbers){
// Build heap (rearrange array)
for (int i = numbers.size() / 2 ; i >= 0; i--){
bubble_down(numbers, i, numbers.size());
}
}
```
### Activity 12: In-place heap sort
```c++
void heap_sort(std::vector<int> &numbers){
// Build heap (rearrange array)
heapify(numbers);
// One by one extract an element from heap
for (int i = numbers.size()-1; i >= 0; i--) {
std::swap(numbers[0],numbers[i]);
bubble_down(numbers, 0, i);
}
};
```
### Activity 13: General heap sort
```c
template<typename T>
void bubble_down(std::vector<T> &values, size_t index, size_t count){
auto largest = index;
auto l = 2 * index + 1;
auto r = 2 * index + 2;
if (l < count && values[l] > values[largest])
largest = l;
if (r < count && values[r] > values[largest])
largest = r;
if (largest != index) {
std::swap(values[index], values[largest]);
bubble_down(values, largest, count);
}
}
// Activity 11
template<typename T>
void heapify(std::vector<T> &numbers){
// Build heap (rearrange array)
for (int i = numbers.size() / 2 ; i >= 0; i--){
bubble_down(numbers, i, numbers.size());
}
}
template<typename T>
void heap_sort(std::vector<T> &numbers){
// Build heap (rearrange array)
heapify(numbers);
// One by one extract an element from heap
for (int i = numbers.size()-1; i >= 0; i--) {
std::swap(numbers[0],numbers[i]);
bubble_down(numbers, 0, i);
}
}
```
## Looking back
### What we've learnt
- Understand what heap is and its time complexity
- Differentiate binary heap and BST
- Implementing operations on heap
### What were the surprises
Nothing
### What problems we've encountered
Nothing
### What was or still is unclear
Nothing
### How did the group perform?
As good as always
Sign in with Wallet
Connect another wallet