Week 11 - Heaps

# Week 11 - Heaps ## Team Team name Group 2 Date: 21/5/2021 Members: Zahir Josefina Len Bauer Sebastian Wojciechowski | Role | Name | |-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------|------| | **Facilitator** keeps track of time, assigns tasks and makes sure all the group members are heard and that decisions are agreed upon. |Zahir Josefina | | **Spokesperson** communicates group’s questions and problems to the teacher and talks to other teams; presents the group’s findings. |Len Bauer| | **Reflector** observes and assesses the interactions and performance among team members. Provides positive feedback and intervenes with suggestions to improve groups’ processes. | Zahir Josefina | | **Recorder** guides consensus building in the group by recording answers to questions. Collects important information and data. | Sebastian Wojciechowski | ## Activities ### Activity 1: Comparing different data structures | Data Srtuctures | Find-min | Delete-min | Insert | |--- | --- |--- | -- | |Sorted arrays | O(1) | O(1) | O(log n) | |Sorted linked list | O(1) | O(1) | O(n) | |Balanced BST | O(logn) | O(logn) | O(logn) | ### Activity 2: Storing the minimum value in the root node The implementation of a balanced binary tree would rotate right untill the left child node of the root node will be empty ( nullptr ). This approach however, most likely won't keep the tree balanced. ### Activity 3: Identify valid heaps Both 1 and 3 are valid min-heaps. The second tree on the other hand does not follow the heap invariant child nodes of node 29 and node 37 should be lower to keep that invariant. ### Activity 4: Do it yourself Step 1: attaching value of 4 to the right of 13 Step 2: swapping values 4 and 13 Step 3: swapping value 4 and 5 ### Activity 5: Worst-case time complexities | Data Structure | Find-min | Delete-min | Insert | Find | | -------- | -------- | -------- | -- | -- | | Balanced BST | O(log n) | O(log n) | O(log n)| O(log n)| | Binary min-heap | O(1) | Θ(log n) | O(log n)| O(n) | ### Activity 6: Moving to arrays If we count left leaf and right leaf as different positions then we can add 53 at 8 positions (under nodes 29, 23, 47 and 17). If we don't want to have any gaps in the array's data we should insert it at index 11 which would be the left leaf of node 87. This foces us to swap the values to keep the invariant. ### Activity 7: Index computations And that's how you insert code blocks: ```c= int minheap::parent_index(int index) const { if(index==0) { return -1; } return (index-1)/2; } int minheap::left_child_index(int index) const { if ((2 * index + 1) < (int) m_size) { return (2*index + 1); } return -1; } int minheap::right_child_index(int index) const { if ((2 * index + 2) < (int) m_size) { return (2*index + 2); } return -1; } ``` ### Activity 8: Implement the find-min operation ```c= const task &minheap::mininum() const { return m_values[0]; } ``` ### Activity 9: Bubbling up ```c= void minheap::bubble_up(int index) { int parentIdx = parent_index(index); int currentIdx = index; while (currentIdx > 0 && m_values[parentIdx] > m_values[currentIdx]) { swap(currentIdx,parentIdx); currentIdx = parentIdx; parentIdx = parentIdx/2; } } ``` ### Activity 10: Bubbling down ```c= void minheap::bubble_down(int index) { int childLeft = left_child_index(index); int childRight = right_child_index(index); if (childLeft >= 0 && childRight >= 0 && m_values[childLeft] > m_values[childRight]) { swap(childLeft, childRight); } if (childLeft > 0 && m_values[index] > m_values[childLeft]) { task temp = m_values[index]; m_values[index] = m_values[childLeft]; m_values[childLeft] = temp; bubble_down(childLeft); } } ``` ### Activity 11: Bottom up - do it yourself || i:0 |i:1 | i:2|i:3|i:4|i:5|i:6| | -------- | -------- | -------- | -------- | -------- | -------- | -------- | -------- | | Initial array |7|5|6|1|2|3|4| | After 1 swap |7|5|3|1|2|6|4| | After 2 swaps |7|1|3|5|2|6|4| | After 3 swaps |1|7|3|5|2|6|4| | After 4 swaps |1|2|3|5|7|6|4| So this takes 4 swaps. ### Activity 12: Turning vectors into heaps | Number of values|Number of|swaps| | -------- | -------- | -------- | ||Top-down|Bottom-up | |5|4|3| |10|11|8| |20|27|18| |50|76|47| |100|163|97| |200|338|197| |500|861|494| |1000|1754|994| - What is the worst-case time complexity when bubbling values up, from top to bottom? O(n * 2^n + logn * 2^logn) - What is the worst-case time complexity when following the bottom-up approach, bubbling values downwards? O(1.5 * n * log n + n) - Which of the two strategies does the function std::make_heap in the C++ standard library use? It uses bottom-up approach, because it has less time complexity ### Activity 13: Heaps and sorting CODE: ```c= minheap heap; heap << 1 << 4 << 5 << 6 << 2 << 3 << 8 << 2 << 10 << 9 ; for (int i = 0; i < heap.size(); ++i) { std::cout << heap.values()[i].priority << " "; } std::cout << std::endl; while (heap){ heap.delete_min(); for (int i = 0; i < heap.size(); ++i) { std::cout << heap.values()[i].priority << " "; } std::cout << std::endl; } ``` ### Activity 14: In-place heap sort (optional) ## Look back ### What we've learnt This week we learned of binary Heap and how to implement it. ### What were the surprises There weren't many surprises this week maybe how more effecient the heap appears to be compared to the normal binary tree. ### What problems we've encountered We didn't encounter many problems related to the activities. ### What was or still is unclear Theory wise everything is clear. ### 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? The Collabration of the group was pretty good , we had some diffuculty meeting up after the first meeting due to Project System but aside from that the perfermance was good.