PPractick

The problem

A task scheduler needs a priority queue where the smallest deadline always comes out first, and the platform has no standard library. Implement a binary min-heap over an array with:

• insert(x)
• getMin()
• extractMin() (−1 if empty)
• size()
• deleteKey(i), which removes whatever element sits at heap index i, for example a cancelled task

Insertion sifts up, extraction moves the last element to the root and sifts down, and deleting index i puts the last element at i and sifts whichever direction is needed.

Example: insert(4), insert(2), extractMin() → 2, insert(6), deleteKey(0), extractMin() → 6, extractMin() → -1.

Function signature

class MinHeap {
public:
    void insert(int x);
    int getMin() const;      // -1 if empty
    int extractMin();        // -1 if empty
    void deleteKey(int i);   // ignored if i is out of range
    int size() const;
};

Test cases

Operations	Output	Explanation
insert(4) insert(2) extractMin() insert(6) deleteKey(0) extractMin() extractMin()	2 6 -1	deleteKey(0) removes 4, the root at that moment
insert(3) insert(1) insert(2) getMin() size()	1 3
extractMin() on an empty heap	-1
insert(5) insert(5) extractMin() extractMin()	5 5	Duplicates
insert(9) insert(7) insert(8) extractMin() extractMin() extractMin()	7 8 9	Sorted order out

(Confirm: indices in deleteKey refer to positions in the heap's array; −1 signals "empty".)

How interviewers phrase it

• "Implement a binary min heap with insertKey, deleteKey and extractMin" (GeeksforGeeks "Operations on Binary Min Heap").

Clarifying questions to ask

1. What should extractMin or getMin return on an empty heap? (−1.)
2. Does deleteKey take an array index or a value? (An index.)
3. Fixed capacity or growable? (Growable, using a vector.)

Follow-ups to expect

1. "How does insert work?"
2. "How does extractMin work?"
3. "How do you delete an arbitrary index?"
4. "How would you support 'decrease key by value'?"
5. "Complexity?"

Related questions

• Check if an array represents a min heap Medium
• Convert Min Heap to Max Heap Medium
• K-th Largest element in an array Medium
• Kth smallest element in an array [use priority queue] Medium
• Task Scheduler Medium
• Hand of Straights Medium

All 474 dsa interview questions

DSA mock interviews · System design interview questions · Free mock interview practice · Browse interviewers · Sign in