Week 6 Learning journal- CST370

This week, I mainly learned about two major topics: Heaps and Hashing. I started by learning about the Max Heap, which is a really efficient way to implement a priority queue. It was interesting to see how a complete binary tree can be represented using a simple array with 1-based indexing. This trick makes navigating between parents and children (using i/2, 2*i, etc.) super fast without needing pointers. I also spent time understanding the core operations like insertion (where you add to the end and sift up) and deletion (swapping the root with the last element and sifting down). One key takeaway for me was realizing that building a heap from scratch can be done in O(N) time using a bottom-up approach, which is much better than the O(N \log N) approach of inserting elements one by one.

The second part of the module focused on Hashing, which is all about fast data retrieval. I learned how hash functions map keys to table indices and why handling collisions is so important. The concepts of separate chaining (using linked lists) and linear probing (checking the next slot) made a lot of sense for resolving conflicts. I also learned about the importance of the load factor, if the table gets too full, performance drops, so we have to resize and rehash everything, usually to a new prime-sized table to keep things efficient.

Finally, applying these concepts in hw5_1 really solidified my understanding. Writing the C++ code to check for the heap property and implement the siftDown function was a great exercise. It was satisfying to see the theoretical "array-as-a-tree" concept actually working in code to organize data efficiently. Overall, this week showed me how choosing the right data structure, whether it's a heap for sorting/priority or a hash table for searching, makes a huge difference in algorithm performance.