Priority Queues (MinPQ)

Problem & Motivation:

Design a priority queue that efficiently supports removing the smallest item and updating priorities while maintaining correct ordering.

Data & Approach:

• Began with a simple array-based implementation to establish correct behavior for core priority queue operations.
• Implemented a binary heap using the array representation described in class, maintaining the heap-order property through swimming and sinking.
• Used tests to confirm that the heap structure preserved the correct parent/child relationships after each operation.
• Compared runtimes of the different implementations to see how representation impacts efficiency.

Results:

• The heap-based implementation handled remove-smallest and priority updates much more efficiently than a simple array scan.
• Maintained the heap-order property across a variety of operations and input sizes.

Limitations:

Focused only on the binary heap representation and the operations covered in the course; does not include additional priority queue variants.