MediumLow-Level DesignAsked in 20245 min read

Priority queue binary heap

Q: Priority queue binary heap

**Target Audience:** Engineers preparing for practical JavaScript coding interviews. **Difficulty:** Medium > **How to read this doc:** the real, defining correctness property of a heap — that repeated `extractMin()` calls always return values in genuinely sorted order, regardless of the original INSERTION order — was verified directly with a real, randomly-shuffled 9-number sequence. ## 1. The problem, restated A binary min-heap is a complete binary tree (stored efficiently as a plain array, using index arithmetic instead of real node/pointer objects) satisfying the HEAP PROPERTY: every parent is less than or equal to both its children. This structure lets `insert` and `extractMin` (removing the overall smallest element) both run in O(log n), genuinely faster than a naive sorted-array or linear-scan approach. ## 2. Clarifying questions a strong candidate asks | Question | Why it matters | | :--- | :--- | | Array-backed with index arithmetic, or a real tree of node objects? | Arra

3.8k views

51 of 154

The problem

Problem, as an interviewer would state it: "Implement a priority queue using a binary MIN-HEAP, backed by a plain array — support insert(value) and extractMin(), both in O(log n)."

Examples:

Code

const heap = new MinHeap();
[5, 3, 8, 1].forEach(n => heap.insert(n));
heap.extractMin(); // 1
heap.extractMin(); // 3

Clarifying questions expected:

Is a plain array-backed heap (using index arithmetic for parent/child relationships) the expected approach, or a real linked tree structure?
Should this be a min-heap or a max-heap — and does the comparison logic need to be configurable?
What should extractMin() return on an empty heap?

Code / implementation expected: Yes — real, direct proof: insert a real, randomly-ordered sequence, then confirm repeated extractMin() calls produce the exact correct, genuinely sorted order.

js-coding
utility
algorithm

Try it yourself

Sketch your approach before you read the solution. That is what the interview tests.

Stuck? Get a hint.

A short nudge toward the approach. It will not give the answer away.

Solution

Target Audience: Engineers preparing for practical JavaScript coding interviews. Difficulty: Medium

How to read this doc: the real, defining correctness property of a heap — that repeated extractMin() calls always return values in genuinely sorted order, regardless of the original INSERTION order — was verified directly with a real, randomly-shuffled 9-number sequence.

1. The problem, restated

A binary min-heap is a complete binary tree (stored efficiently as a plain array, using index arithmetic instead of real node/pointer objects) satisfying the HEAP PROPERTY: every parent is less than or equal to both its children. This structure lets insert and extractMin (removing the overall smallest element) both run in O(log n), genuinely faster than a naive sorted-array or linear-scan approach.

2. Clarifying questions a strong candidate asks

| Question | Why it ma

The solution is hidden so you can try first

5 min read · 9 sections

Run the code

Edit the code and run it here. Each console line with an expected value becomes a test.

JavaScriptReal, direct proof: inserting a randomly shuffled sequence and repeatedly calling extractMin() produces the exact correct, genuinely sorted ascending order

Practice

Discussion

Other approaches, follow-ups and how it went in real interviews.

No comments yet. Share how you would answer it.

Question 51 of 154 in JavaScript coding

Keep your momentum going.

Mark this question solved to track your progress, then take the next one while it is fresh.

All JavaScript coding questions

Up nextMedium→

HTML template compiler

Continue