Implement a Priority Queue from Scratch with Custom Ordering and Stable Ties

Implement a priority queue yourself, without using the language's built-in heap module or priority-queue class. It must support: - `push(item)`: add an item. - `peek()`: return the highest-priority item without removing it. - `pop()`: remove and return the highest-priority item. - a size query and an emptiness check. Choose the underlying data structure, implement the operations, and state the time and space complexity of each. For practice, treat "highest priority" as "smallest key" by default and let the caller supply the ordering, so the same class can serve as a max-queue or order records by one of their fields. ```hint Keep only the best in place Look for a structure that always knows where the best element is without keeping everything else fully sorted. ``` ```hint Test the boundaries Dry-run a removal when only one or two items remain, and when two candidates for the top have equal priority. ``` ### Constraints and Clarifications - Plain arrays or lists and basic language features are allowed; library heaps and priority queues are not. - Calling `peek` or `pop` on an empty queue must fail in a defined, documented way. - Duplicate priorities are allowed. ### Clarifying Questions - Should items with equal priority leave in the order they were inserted? - Will callers need to change an item's priority, or remove an arbitrary item, after inserting it? - Will several threads share the same queue? - Is the queue ever built from a large existing collection in one go? ### What a Strong Answer Covers - A structure choice justified against the alternatives (unsorted array, sorted array, balanced search tree) - Insertion and removal that correctly restore the ordering invariant, including the index arithmetic - Complexity of every operation and of building the queue from n existing items - Defined behavior for an empty queue, ties and caller-supplied ordering - A dry run or tests that exercise the edge cases ### Follow-up Questions - How would you support changing the priority of an item that is already in the queue? - How can you build the queue from an existing list of n items faster than n separate inserts, and why is that bound linear? - How would you make the queue safe for several producer and consumer threads, with consumers waiting while it is empty? - When would a heap with more than two children per node outperform a binary one?