JavaScript Notes

Priority Queue in JavaScript — Min Heap Implementation Guide

Master the Priority Queue data structure in JavaScript using a min-heap. Learn enqueue, dequeue by priority, heap operations, Dijkstra

A Priority Queue is a data structure where each element has a priority, and the element with the highest (or lowest) priority is dequeued first — regardless of when it was inserted. It doesn't follow FIFO; it follows "most important first."

💡 Key insight: A Priority Queue is most efficiently implemented with a binary heap — it gives O(log n) insertion and O(log n) extraction, far better than sorting on every insertion (O(n log n)).

Simple Array-Based Priority Queue (O(n) — Easy to Understand)

Example

class SimplePriorityQueue { #items = []; enqueue(value, priority) { this.#items.push({ value, priority }); this.#items.sort((a, b) => a.priority - b.priority); } dequeue() { if (this.isEmpty()) throw new Error("Queue is empty"); return this.#items.shift().value; } peek() { return this.isEmpty() ? null : this.#items[0].value; } isEmpty() { return this.#items.length === 0; } size() { return this.#items.length; } } const pq = new SimplePriorityQueue(); pq.enqueue("Low task", 10); pq.enqueue("Critical task", 1); pq.enqueue("Medium task", 5); pq.enqueue("Urgent task", 2); console.log("Next:", pq.peek()); while (!pq.isEmpty()) { console.log("Processing:", pq.dequeue()); }

Output

"Next: Critical task"
"Processing: Critical task"
"Processing: Urgent task"
"Processing: Medium task"
"Processing: Low task"

Efficient Min-Heap Priority Queue (O(log n))

Example

class MinHeapPriorityQueue { #heap = []; get size() { return this.#heap.length; } isEmpty() { return this.size === 0; } enqueue(value, priority) { this.#heap.push({ value, priority }); this.#siftUp(this.size - 1); } dequeue() { if (this.isEmpty()) throw new Error("Queue is empty"); const min = this.#heap[0]; const last = this.#heap.pop(); if (this.size > 0) { this.#heap[0] = last; this.#siftDown(0); } return min.value; } peek() { return this.isEmpty() ? null : this.#heap[0].value; } #siftUp(i) { while (i > 0) { const parent = Math.floor((i - 1) / 2); if (this.#heap[parent].priority <= this.#heap[i].priority) break; [this.#heap[parent], this.#heap[i]] = [this.#heap[i], this.#heap[parent]]; i = parent; } } #siftDown(i) { while (true) { let smallest = i; const left = 2 * i + 1; const right = 2 * i + 2; if (left < this.size && this.#heap[left].priority < this.#heap[smallest].priority) smallest = left; if (right < this.size && this.#heap[right].priority < this.#heap[smallest].priority) smallest = right; if (smallest === i) break; [this.#heap[smallest], this.#heap[i]] = [this.#heap[i], this.#heap[smallest]]; i = smallest; } } toArray() { return [...this.#heap].sort((a,b) => a.priority - b.priority).map(e => `${e.value}(${e.priority})`); } } const pq = new MinHeapPriorityQueue(); pq.enqueue("Send email", 5); pq.enqueue("Critical bug", 1); pq.enqueue("Write tests", 8); pq.enqueue("Deploy fix", 2); pq.enqueue("Code review", 4); console.log("Queue:", pq.toArray()); console.log("Next:", pq.peek()); while (!pq.isEmpty()) { console.log("Process:", pq.dequeue()); }

Output

"Queue: ['Critical bug(1)', 'Deploy fix(2)', 'Code review(4)', 'Send email(5)', 'Write tests(8)']"
"Next: Critical bug"
"Process: Critical bug"
"Process: Deploy fix"
"Process: Code review"
"Process: Send email"
"Process: Write tests"

Heap Structure Visualised

Example

Min Heap after inserting (1,2,4,5,8): 1 ← priority 1 (root = minimum) / \ 2 4 / \ 5 8 Array representation: [1, 2, 4, 5, 8] Parent of index i: Math.floor((i-1)/2) Left child of i: 2*i + 1 Right child of i: 2*i + 2

Time Complexity

Operation	Array-based	Min-Heap
`enqueue`	O(n log n) (sort)	O(log n) (sift up)
`dequeue`	O(n) (shift)	O(log n) (sift down)
`peek`	O(1)	O(1)
`build` from array	O(n log n)	O(n) (heapify)
Space	O(n)	O(n)

Real-World Application: Dijkstra's Shortest Path

Priority queues are the core of Dijkstra's algorithm:

Example

Output

{ A: 0, B: 3, C: 2, D: 6 }

When to Use a Priority Queue

✅ Use a Priority Queue when:

Tasks have different urgency levels (OS process scheduling, hospital triage)
Dijkstra's shortest path algorithm
**A\* pathfinding** in games
Huffman encoding (data compression)
Median finder (two heaps)
K largest/smallest elements from a stream

Common Mistakes

Forgetting to sift after extraction — after swapping root with last element, you must sift down to restore heap property.
Using a sorted array — O(n log n) enqueue is fine for small inputs but kills performance at scale.
Not handling equal priorities — decide on a tiebreaker (e.g., FIFO for equal priorities) in production code.
Modifying priorities after insertion — changing a priority requires removing and re-inserting the element (or a "decrease-key" operation, which is complex).

Interview Questions

Q1. What is a Priority Queue and how does it differ from a regular queue?

A regular queue is FIFO — the first element added is the first removed. A Priority Queue dequeues the highest priority element first, regardless of insertion order.

Q2. What data structure is typically used to implement an efficient Priority Queue?

A binary heap (min-heap or max-heap). It provides O(log n) enqueue and dequeue operations, much better than a sorted array's O(n log n) or a sorted linked list's O(n).

Q3. What is a min-heap vs max-heap?

In a min-heap, the smallest value is at the root and dequeued first. In a max-heap, the largest value is at the root and dequeued first. Choose based on whether lower or higher values have higher priority.

Q4. What is the time complexity of inserting into a heap?

O(log n) — the new element is added at the end of the array, then sifted up by swapping with its parent until the heap property is restored. In the worst case, it travels from leaf to root: log₂(n) steps.

Q5. How is a binary heap represented as an array?

The root is at index 0. For any node at index i: left child = 2i + 1, right child = 2i + 2, parent = Math.floor((i-1)/2).

Q6. Where is a Priority Queue used in real JavaScript applications?

Task schedulers (run highest-priority job first), Dijkstra's algorithm in routing apps (Google Maps), A* pathfinding in games, huffman encoding for file compression, top-K problems (find K most frequent words).

Q7. How would you find the K smallest elements in an array using a priority queue?

Build a max-heap of size K. For each element in the array, if it's smaller than the heap's max (root), replace the root and heapify. The heap contains the K smallest elements at the end. Time: O(n log K).

Key Takeaways

Priority Queue dequeues the highest-priority element first — not FIFO.
Efficient implementation uses a binary heap: O(log n) enqueue and dequeue.
A min-heap prioritises lower numbers; a max-heap prioritises higher numbers.
Heap stored as an array: parent at floor((i-1)/2), children at 2i+1 and 2i+2.
Core use cases: task scheduling, Dijkstra's algorithm, A* pathfinding, Huffman coding, K-smallest/largest problems.

Exam Focus

Revise definitions, diagrams, examples, and short-answer points for Priority Queue in JavaScript — Min Heap Implementation Guide.

Interview Use

Prepare one clear explanation, one practical example, and one common mistake for this JavaScript Master Course topic.

Search Terms

javascript-complete-guide, javascript master course, javascript, complete, guide, data, structures, priority

Continue learning this concept

Data StructuresQueue Data Structure in JavaScript — FIFO, Enqueue & Dequeue ExplainedMaster the Queue data structure in JavaScript. Learn FIFO principle, enqueue/dequeue operations, circular queue, priority queue, real-world examples like task scheduling, and interview Q&A.Data StructuresDeque (Double-Ended Queue) in JavaScript — Complete GuideLearn the Deque (Double-Ended Queue) data structure in JavaScript. Add and remove from both ends, implement with arrays and classes, explore sliding window use cases, and answer interview questions.Data StructuresLinked List in JavaScript — Nodes, Pointers & Operations GuideMaster the Linked List data structure in JavaScript. Learn singly and doubly linked lists, node creation, insertions, deletions, traversal, and linked list interview questions with code examples.Data StructuresJavaScript Map — Key-Value Data Structure Complete GuideMaster the JavaScript Map data structure. Learn Map vs Object, set/get/has/delete/iteration, any-type keys, insertion order, WeakMap, and Map interview questions with real code examples.Data StructuresJavaScript Numbers — IEEE 754, Precision, and Number Methods GuideMaster JavaScript Numbers: IEEE 754 floating point, precision issues, NaN, Infinity, BigInt, Number methods like toFixed, parseInt, parseFloat, and numeric interview questions with examples.Data StructuresJavaScript Set — Unique Values Data Structure GuideMaster the JavaScript Set data structure for storing unique values. Learn add, has, delete, iteration, Set operations (union, intersection, difference), WeakSet, and Set interview questions.

PreviousJavaScript Numbers — IEEE 754, Precision, and Number Methods Guide NextQueue Data Structure in JavaScript — FIFO, Enqueue & Dequeue Explained