Skip to content
Tutorials Center
My learning

Topics

Lesson 148 of 156 Β· Data Structures and Algorithms

Heaps, Priority Queues and Deques

Build a binary heap, a generic PriorityQueue with a comparator and a ring-buffer deque in JavaScript, then use them for scheduling, top-k and Dijkstra.

A normal queue is fair: whoever arrives first is served first. Real life is often less fair, and for good reasons. An emergency room treats the most urgent patient next, not the one who came in first. A download manager runs small, high-priority files before large background ones. A route planner always looks at the cheapest road it hasn't explored yet. All of these need a priority queue: a collection where you can add items in any order and always take out the "most important" one.

JavaScript has no built-in priority queue. You could keep an array sorted, but every insert would then cost O(n). The classic answer is a binary heap, which does both insert and remove in O(log n) using nothing more than a plain array and some index arithmetic. In this lesson you will build a heap step by step, turn it into a reusable PriorityQueue class, use it for scheduling, top-k and Dijkstra's shortest-path algorithm, and finish with its useful cousin, the deque, built on a ring buffer.

If Big-O notation is new to you, read Searching and Sorting Algorithms first; this lesson uses it throughout.

What a heap is

A binary heap is a binary tree with two rules:

  1. Shape rule. The tree is complete: every level is full except possibly the last, and the last level fills from left to right. There are never gaps.
  2. Heap rule. In a min-heap, every parent is smaller than or equal to its children. (In a max-heap, every parent is larger or equal.)
TEXT
            2
         /     \
        5       3
       / \     / \
      9   6   8   4
     /
    12

The heap rule says nothing about the order of siblings: 5 sits left of 3 even though it's bigger. A heap is not sorted. It only guarantees one thing, and that is all a priority queue needs: the smallest item is always at the root.

Because the tree is complete, its height is about logβ‚‚(n). A heap of a million items is only 20 levels deep, and every operation you'll write walks at most one path from the root to a leaf. That is where the O(log n) comes from.

Storing a tree in an array

The shape rule pays off in a surprising way: a complete tree needs no node objects or pointers. Write the items level by level, left to right, into an array, and the tree structure follows from the indexes alone:

Relationship Index formula
Left child of i 2 * i + 1
Right child of i 2 * i + 2
Parent of i Math.floor((i - 1) / 2)

The tree above becomes [2, 5, 3, 9, 6, 8, 4, 12]. Index 0 holds the root, indexes 1 and 2 hold its children, 3 to 6 hold the grandchildren, and so on. Run this to print the array as levels and check the heap rule for every parent:

JS An array viewed as a tree

Press Run (or Ctrl + Enter) to see the console output here.

No output.

The last line fails because 1 sits below 5. Checking each item against its parent is enough to verify the whole heap, since every parent-child pair gets compared exactly once.

Push and pop: sifting up and down

Both operations first keep the shape rule, then repair the heap rule along a single path.

Push (insert): put the new item at the end of the array, the next free spot in the bottom row. It may be smaller than its parent, so sift it up: swap it with its parent until the parent is smaller or it reaches the root.

Pop (remove the minimum): the answer is at index 0. To fill the hole without breaking the shape, move the last item to the root. It is probably too big for the top, so sift it down: swap it with its smaller child until both children are bigger or it reaches the bottom.

Peek just reads index 0, which is O(1).

JS A min-heap with push, pop and peek

Press Run (or Ctrl + Enter) to see the console output here.

No output.

Watch the arrays as you push: each new number lands at the end and climbs only as far as it must. Popping everything gives the numbers in ascending order, even though the array was never sorted. That observation is the whole idea behind heap sort.

The (i - 1) >> 1 trick divides by two and drops the fraction in one fast step. It works for any index below about two billion, because >> converts to a 32-bit integer (see Bitwise Operators). Math.floor((i - 1) / 2) is clearer and nearly as fast; use whichever you find easier to read.

Building a heap in one go: heapify

If you already have all the items, pushing them one at a time costs O(n log n). There's a faster way called heapify: treat the array as a broken heap and sift down every parent, starting from the last parent and moving back to the root. Leaves (the second half of the array) are already valid one-item heaps, so they're skipped.

It sounds like it should also be O(n log n), but most nodes sit near the bottom, where sifting down is short. The total work adds up to O(n). Heapify plus repeated pops gives heap sort, an O(n log n) sort that needs no extra array:

JS Heapify and heap sort in place

Press Run (or Ctrl + Enter) to see the console output here.

No output.

Even for 100,000 items in the worst order, heapify makes fewer swaps than there are items. That is the O(n) bound in action. Heap sort itself is not stable and usually slower than the built-in sort() in practice, so treat it as a lesson in how heaps work, not a replacement for array.sort().

A generic PriorityQueue with a comparator

A heap of bare numbers is a good exercise, but real queues hold objects: tasks, network packets, graph nodes. The fix is the same one sort() uses: take a comparator function that returns a negative number when a should come out before b. Pass (a, b) => a - b for a min-heap of numbers, (a, b) => b - a for a max-heap, or compare any property you like.

One subtle issue: heaps are not stable. Two tasks with the same priority can come out in either order. If that matters (it usually does for scheduling), stamp each item with an increasing sequence number and use it as a tie-breaker.

JS A reusable PriorityQueue class

Press Run (or Ctrl + Enter) to see the console output here.

No output.

"charge card" and "refund order" share priority 1 and come out in the order they were added, thanks to seq. The private #heap, #less and #swap keep the internals hidden (see Private and Static Members), so code using the queue can only push, pop and peek.

Changing a priority. Heaps can't find an item quickly, so "update the priority of task X" is awkward. The common trick, used below in Dijkstra, is lazy deletion: push the item again with its new priority and, when an outdated copy pops out later, just skip it.

Top-k: the best few out of many

"Show the 3 highest scores out of a million" doesn't need a full sort. Keep a min-heap of size k. For each new item, push it; if the heap grows past k, pop the smallest. The heap's root is always the weakest of the current top k, so anything smaller is thrown away right away. This costs O(n log k) time and only O(k) memory, which also works on data streaming in one item at a time.

JS Top-k with a small min-heap

Press Run (or Ctrl + Enter) to see the console output here.

No output.

Dijkstra's shortest path

The Data Structures lesson found routes with breadth-first search, which counts edges. When edges have costs (minutes, kilometers), you need Dijkstra's algorithm: always expand the unvisited place with the smallest known total cost. "Always take the smallest" is exactly what a priority queue does, so the heap turns Dijkstra from O(VΒ²) into O((V + E) log V).

JS Dijkstra with a priority queue

Press Run (or Ctrl + Enter) to see the console output here.

No output.

The direct road from Depot to Bridge takes 7 minutes, but going through Mill takes 2 + 3 = 5, and Dijkstra finds it. The continue line is lazy deletion at work: when a cheaper route to a node is found, the old, more expensive entry stays in the heap and is simply ignored when it surfaces. Dijkstra requires non-negative edge costs; with negative costs, use Bellman-Ford instead.

Priority queues show up in many other places: event-driven simulations (pop the next event by time), timers in runtimes such as Node.js, merging many sorted lists, A* path finding in games, and Huffman compression.

Deques: a queue with two ends

A deque (pronounced "deck", short for double-ended queue) lets you add and remove at both the front and the back in O(1). JavaScript arrays have all four operations (push, pop, unshift, shift), but unshift and shift may move every item.

A ring buffer avoids that. It's a fixed-size array plus a head index and a length. Positions wrap around the end with the remainder operator %, so the "front" can be anywhere in the array and nothing ever needs moving. When the buffer is full, copy the items into an array twice as big. That copy is O(n) but rare, so each operation is O(1) on average (amortized).

JS A ring-buffer deque

Press Run (or Ctrl + Enter) to see the console output here.

No output.

The sliding-window maximum shows why deques matter: new readings join at the back, old ones leave from the front, and readings that can never be the maximum are thrown out from the back. Every index enters and leaves once, so the whole scan is O(n). Deques also power undo histories with a size limit (drop the oldest from the front), work-stealing schedulers, and breadth-first searches on 0/1-weighted graphs.

Which structure for which job?

You need to… Use Cost
Take items in arrival order Queue O(1) add and remove
Take the smallest (or largest) item next Priority queue (binary heap) O(log n) push/pop, O(1) peek
Add and remove at both ends Deque (ring buffer) O(1) amortized at both ends
Find any item by key Map O(1)
Keep everything in sorted order and walk it Sorted array or balanced tree O(n) or O(log n) insert

For a few dozen items, a plain array with sort() or shift() is often fine and easier to read. Reach for these structures when the collection gets large or the operations run in a hot loop, and measure (see Performance).

Check your understanding

Quick check Β· 5 questions

of 5 answered You scored / 5 Β· perfect!

  1. 1. In a binary heap stored in an array, where are the children of the item at index 4?

    The children of index i are at 2i + 1 and 2i + 2, so index 4 has children at 9 and 10. Index 1 is its parent: Math.floor((4 - 1) / 2).
  2. 2. What does the min-heap rule guarantee?

    Each parent is smaller than or equal to its children, so the minimum is at index 0. Siblings and levels are not sorted.
  3. 3. Why does pop() move the last array item to the root before sifting down?

    Removing the last array slot keeps the shape rule. The moved item may be out of place, so it sifts down along one path, which is O(log n).
  4. 4. You need the 10 largest values from a stream of 5 million numbers. What is the most efficient approach?

    A size-k min-heap keeps the current top 10 with the weakest at the root. It needs O(n log k) time and only O(k) memory.
  5. 5. What makes a ring-buffer deque fast at both ends?

    The head index moves instead of the items. Growing copies everything, but rarely, so every operation is O(1) amortized.

Summary

  • A binary heap is a complete binary tree where every parent beats its children; the best item is always at the root.
  • Stored in an array, the children of i are at 2i + 1 and 2i + 2, and its parent at Math.floor((i - 1) / 2).
  • Push appends and sifts up; pop moves the last item to the root and sifts down; both are O(log n). Peek is O(1).
  • Heapify builds a heap from an array in O(n); heapify plus repeated pops is heap sort.
  • A PriorityQueue class takes a comparator; add a sequence number to keep equal priorities in arrival order, and use lazy deletion instead of updating priorities.
  • Heaps power scheduling, top-k (a size-k min-heap) and Dijkstra's algorithm.
  • A deque built on a ring buffer adds and removes at both ends in O(1) amortized time.

Next: Where to Go Next: Libraries and Frameworks β€” how React, Vue, Svelte and friends build on everything you've learned.