Implement a binary min-heap and use it to order courses with prerequisites

In one coding round of about 30 minutes, you are asked to write a heap yourself and then to use it in a variant of the course-scheduling problem.

Constraints and Clarifications

• Do not use heapq, queue.PriorityQueue or any other priority-queue library, and do not sort the whole list on each operation.
• Heap elements are mutually comparable values, such as integers or tuples of integers.
• The exact twist of the course-scheduling variant was not reported. This version makes the order unique by always taking the smallest-numbered available course; ask the interviewer which variant they intend.

Clarifying Questions

• Should pop and peek on an empty heap raise an error or return a sentinel value?
• Besides push, pop and peek, does the heap need other operations, such as removing an arbitrary element or changing a priority?
• Must Part 2 use the heap from Part 1?

Part 1 — A binary min-heap

Implement a MinHeap class with:

• push(x): insert x;
• pop(): remove and return the smallest element;
• peek(): return the smallest element without removing it;
• __len__(): the number of elements;
• a constructor that accepts an existing list of elements and builds the heap in linear time.

What This Part Should Cover

• The array layout and the parent and child index arithmetic
• Restoring order after push and after pop, including which child to swap with
• Linear-time construction and the argument for why it is linear
• Behavior on an empty heap, a single element and duplicate values

Part 2 — Ordering courses with prerequisites

There are n courses labeled 0 to n - 1, and a list of pairs [a, b], each meaning that course b must be completed before course a. Courses are taken one at a time. Return an order in which all n courses can be completed. Whenever more than one course has all its prerequisites completed, take the smallest-numbered one next. If circular prerequisites make it impossible to complete every course, return an empty list. Use your MinHeap from Part 1.

For example, with n = 3 and prerequisites [[0, 1]], courses 1 and 2 are available at the start. Taking 1 makes 0 available, and 0 is now the smallest available course, so the answer is [1, 0, 2].

Clarifying Questions for this Part

• Can the list contain duplicate pairs, or a course that lists itself as its own prerequisite?
• Are all labels guaranteed to lie between 0 and n - 1?

What This Part Should Cover

• Representing the prerequisites and tracking when each course becomes available
• Using the heap to choose the next course so that the order is unique
• Detecting circular prerequisites and returning the empty list
• Time and space complexity in terms of courses and prerequisite pairs