Prompt and context
Implement a meldable min-priority queue for an event scheduler whose task priorities can decrease. A binary heap handles basic operations, but meld and decrease-key add cost. Implement a pairing heap with handles, linking, two-pass merging, deletion, and edge cases.
Pairing heaps were introduced in 1986 as self-adjusting heaps intended to combine simple implementation with good practical performance; the original paper gave only partial complexity analysis. The interview tests whether you separate code correctness, amortized reasoning, and unproven complexity claims.
What the interviewer evaluates
Cover the min-heap invariant, constant-time meld, two-pass sibling pairing, stale handles, cut-and-relink decrease-key, empty and duplicate keys, memory ownership, and trade-offs against binary and Fibonacci heaps.
Clarifying questions to ask
- Is decrease-key required, or only push/pop, and what is the operation mix?
- Must node handles remain stable, and how are stale handles detected?
- Is recursion allowed, and what are maximum heap size and stack budgets?
- Can the comparator throw or change, and are duplicate priorities supported?
- Is the goal teaching clarity, low-constant practical speed, or a strict worst-case proof?
A 30-second answer
“Each node stores a key, payload, parent, first child, and next sibling, with a handle pointing to the node. Link compares two roots and makes the larger root the first child of the smaller root. Delete-min detaches the root, links siblings left to right in pairs, then merges right to left. Decrease-key cuts a non-root and melds it as a root. Track handle state and describe complexity using amortized and established analysis.”
Step-by-step deep dive
Step 1: Define nodes and handles
Store key, payload, parent, first child, and right sibling in each node. A handle points to the node and carries a live marker or generation, preventing decrease-key after deletion. A root has no parent and the sibling-list tail is null.
Node { key, value, parent, firstChild, nextSibling, alive }
Heap { root, size }The comparator only orders values and does not mutate nodes. Treat equal keys as distinct nodes and apply the required stability policy.
Step 2: Implement link and meld
link(a, b) compares two roots, makes the larger-key root the first child of the smaller root, and updates parent and sibling pointers. meld only links two roots; an empty heap returns the other root.
After each pointer update, assert that the root has no parent, each child points back to its parent, and size is unchanged. A debug build can traverse the structure for cycles, but production operations should not perform a linear check every time.
Step 3: Implement insert and find-min
insert creates a singleton heap, melds it with the root, and returns a stable handle. find-min reads the root; an empty heap returns the API’s empty result or error instead of dereferencing null.
If callers retain handles, moving or growing the heap must not invalidate them. Allocate nodes independently or use a stable indirection layer, and document whether the heap owns nodes or only payloads.
Step 4: Implement two-pass delete-min
After removing the root, detach its child list into a root list. In the first pass, link adjacent roots from left to right in pairs; keep the last root when the count is odd. In the second pass, meld the results from right to left.
deleteMin(h):
children = detachChildren(h.root)
pairs = linkAdjacent(children)
newRoot = mergeRightToLeft(pairs)
invalidate(h.root)
h.root = newRoot
h.size -= 1Clear old parent and sibling pointers during merging so the removed root is not retained. Use an iterative list for a long sibling chain to avoid stack overflow.
Step 5: Implement decrease-key
Reject a new key that is not smaller, or define a separate increase-key operation. For the root, update only the key. For a non-root, cut it from its parent’s child list, repair sibling pointers, and meld it as an independent root.
Cutting needs the preceding sibling: scan the parent list, or add a prevSibling pointer and accept extra maintenance. Return an error for a stale handle, a node from another heap, or a destroyed heap.
Step 6: Test invariants and complexity
Use randomized differential tests against a standard priority queue, covering duplicate keys, empty heaps, repeated decrease-key, deleting every node, and random meld. After each operation verify the root is minimal, size matches live nodes, and parent-child links are acyclic.
Separate proven bounds, amortized intuition, and measurements. Pairing-heap insert and meld have small constants, but strict analyses for delete-min and decrease-key are not a license to claim that every operation is worst-case O(log n). State assumptions and compare binary and Fibonacci heaps.
A strong sample answer
I would use parent, first-child, next-sibling pointers and stable handles for link, meld, two-pass delete-min, and decrease-key. A non-root decrease-key is cut from its sibling list before it is melded as a new root; delete-min pairs left to right and merges right to left. I would differential-test against a standard priority queue, check acyclicity and size invariants, and distinguish amortized analysis, worst-case bounds, and practical benchmarks.
Common mistakes
- Changing only the key → heap order and parent links break → cut and meld every non-root decrease-key.
- Reversing the two passes → shape and results are wrong → pair left to right, then merge right to left.
- Using a deleted handle → use-after-free or cross-heap mutation → invalidate and verify ownership.
- Claiming every operation is worst-case O(log n) → complexity has no support → separate amortized, partial analysis, and measurement.
- Recursing through a long sibling list → stack overflow → use an iterative list.
Follow-up questions and responses
Follow-up 1: Why not use a binary heap directly?
Binary heaps have simple array layout and stable bounds; pairing heaps may have smaller constants with meld and frequent decrease-key. Choose using the operation mix, memory locality, and proof requirements.
Follow-up 2: How can decrease-key avoid scanning siblings?
Add a prevSibling pointer or a child-set index, but maintain more pointers on every link and cut. Compare that space and maintenance cost with scanning.
Follow-up 3: How do you delete an arbitrary handle?
Lower its key to negative infinity, call decrease-key, and then delete-min. Ensure the comparator and sentinel are safe, and invalidate the handle correctly.
Follow-up 4: When would you choose a Fibonacci heap?
Consider it when the theoretical decrease-key amortized bound and algorithmic proof matter more than implementation complexity. Engineering code still needs measurements of locality, memory, and real workloads.