CST370 - Week 6

This week, we covered several new topics, including AVL Trees, where we practiced inserting nodes and balancing the tree using rotations. We also learned about 2-3 Trees and how to build them from a set of values. The topic we focused on the most, though, was probably Heaps.

A heap is a special kind of binary tree with two conditions:

• It must be a complete binary tree, meaning every level is completely filled except possibly the last, which is filled from left to right
• 
  
• It must follow the heap property. In a max heap, each parent node is greater than or equal to its children. In a min heap, each parent node is smaller than or equal to its children.

We also learned how to remove a value from a max heap and how to build a heap using a bottom-up method with an array. Additionally, we were briefly introduced to heapsort, a sorting algorithm that works in two steps:

• First, build a max heap from the list of numbers.
• 
  
• Then you repeatedly remove the largest number (which is at the root) and move it to the end of the array. After (n-1) removals, the numbers are sorted.

Lastly, we touched on hashing, which is used to store data efficiently. We also went over important concepts like collisions, load factor, and rehashing.

Overall, this week introduced a few topics I'd plan to revisit to strengthen my understanding. I plan to review the lectures on hashing and heaps, and watch some supplementary videos to better grasp the material.