Week 10 Practice

After reading this week's notes and engaging in the embedded activities and reflections, you should be able to:

• Explain the priority queue abstraction and implement it using binary heaps
• Describe the binary heap structure property (complete binary tree) and order property (max-heap vs min-heap)
• Represent a binary heap using an array and navigate using parent-child index relationships
• Implement heap operations (insert with bubble-up, remove with bubble-down) with proper time complexity
• Define graph terminology including vertices, edges, paths, cycles, directed/undirected, and weighted graphs
• Compare graph representation approaches (adjacency matrix, adjacency list, edge list) and their space-time trade-offs
• Implement breadth-first search (BFS) using a queue and visited set to traverse graphs
• Analyze BFS time complexity O(V + E) and identify its applications

Please refer to this week's readings to review these concepts and skills.

Practice Problems Overview

This week's practice includes 11 problems covering priority queues, binary heaps, and graph representations with BFS:

Binary Heap Fundamentals

1. Verify Heap Order Property (Array) - Determine whether an array representation satisfies max-heap or min-heap properties
2. Verify Heap Order Property (Tree) - Use recursion to verify heap property in tree-represented heaps
3. Top K Largest Elements - Apply min-heap to efficiently find K largest elements
4. Kth Largest Element in Stream - Design a data structure for streaming data with priority queries

Advanced Heap Applications

5. Find Median in Stream - Use two heaps to maintain median as data arrives dynamically
6. Recursive Heap Operations - Implement bubble-up and bubble-down using recursion instead of iteration
7. Priority Queue with FIFO Tiebreaker - Build a stable priority queue where equal priorities are processed FIFO
8. Finding Next Leaf in Linked Tree Heap - Navigate linked heap structures using bit manipulation
9. Heap Update Operation - Implement efficient priority update with HashMap position tracking

Graph Representations and BFS

10. Graph Representation Conversion - Convert between adjacency matrix and adjacency list representations
11. BFS with Three-Color States - Implement BFS using WHITE-GRAY-BLACK coloring scheme for detailed state tracking

Key Patterns: Problems 1-4 demonstrate core heap verification and selection problems. Problems 5-9 explore advanced heap implementation techniques: streaming median, recursion, stability, linked structures, and dynamic updates. Problems 10-11 cover graph representations and enhanced BFS with sophisticated state tracking, building on Day 45's foundation.