EECS 281, Data Structures and Algorithms
Priority Queue Implementations
Four interchangeable priority queue containers behind a common abstract interface: unordered, sorted, binary heap, and pairing heap.
What I built
- Implemented a sorted-array PQ that inserts with lower_bound, a lazily cached unordered PQ, and an array binary heap with fixUp, fixDown, and bottom-up heapify for updatePriorities.
- Built a pairing heap with parent, child, and sibling pointers: O(1) meld-based push, two-pass pairwise merging on pop, and updateElt that cuts a node and re-melds it at the root when its priority increases.
- Wrote the pairing heap's copy constructor, assignment, and destructor using iterative breadth-first traversals.
- Extended the provided test driver to exercise every PQ type, including pointer-based priorities and updatePriorities.