What is a priority queue — and why its array looks unsorted

You're writing a task scheduler for a bot. Tasks keep arriving, each with an urgency. You always need the most urgent one. First instinct:

tasks.push(task);
tasks.sort((a, b) => a.priority - b.priority);
const next = tasks.shift();

It works. But for every new task you re-sort the whole list. A thousand tasks means a thousand sorts of a thousand items. All to get one item — the most urgent.

Here's the surprise: to always know the most urgent item, you don't need the list sorted at all. A weak order is enough. That's a priority queue.

What a priority queue is

A priority queue is a queue where the next one out isn't whoever came first, but whoever has the highest priority.

Like a hospital ER. You came in with a splinter at 9:00 — you wait. Someone with a broken leg arrives at 9:30 — they go before you.

There are just three operations:

• push an item;
• peek at the most important one;
• pop the most important one.

Almost always there's a heap inside.

How a heap works

A heap is a tree with one rule: a parent is more important than its children. That's it. No order between siblings or cousins.

So the key fact: the most important item is always on top. Peeking at it is one step.

A heap lives in a plain array, no node objects. The children of index i sit at 2i + 1 and 2i + 2; the parent is at (i − 1) / 2, rounded down.

That answers the title. Log a heap and you'll see something like [1, 4, 2, 9, 5, 3]. Looks like a bug. But the rule holds: 1 is less than 4 and 2, 4 is less than 9 and 5, 2 is less than 3. A heap isn't sorted — and isn't supposed to be.

Push. The new item goes to the end of the array. Then it "bubbles up": if it beats its parent, they swap. Repeat until it fits.

Pop. Take the top. Move the last item into its place. It "sinks": swaps with the more important child until the rule holds again.

Here's "bubbling up" in code — this is the heap's whole trick:

function push(heap, item) {
  heap.push(item);
  let i = heap.length - 1;
  while (i > 0) {
    const parent = Math.floor((i - 1) / 2);
    if (heap[parent] <= heap[i]) break; // the rule holds
    [heap[parent], heap[i]] = [heap[i], heap[parent]];
    i = parent;
  }
}

The loop only goes up, along one branch. It doesn't even touch the rest of the tree.

How many steps? At most the height of the tree. A heap of a million items is about 20 levels tall. Twenty swaps instead of sorting a million.

Where it helps you

Top 10 from a huge stream. You have a million log lines and want the 10 slowest requests. Sorting everything means holding a million in memory. Instead, keep a heap of exactly 10. New request slower than the fastest one in the heap? Swap it in. At the end, the heap is your top 10. The same trick measures latency "tails" — see percentiles.

Schedulers and timers. Which timer fires next? The one with the nearest time. Node.js keeps its timers in a priority queue internally. Your setTimeout calls live there.

Navigation. Dijkstra's algorithm finds the shortest route. At each step it needs the nearest unvisited point. That's exactly "pop the most important".

Job queues with urgency. A paying user, a retry, a password-reset email — all reasons to go first.

The catch: equal priorities

A heap doesn't promise order among equals. Two tasks with priority 1 may come out in a different order than they arrived.

If that matters, add a counter: [priority, counter++, task]. On a tie, the smaller counter — the one that came first — wins. Python's documentation recommends exactly this.

Does JavaScript have a heap?

Not built in. Python has the heapq module, Java has a PriorityQueue class. In JS you grab a package like @datastructures-js/priority-queue or write one — about 40 lines. A good excuse to ask AI for the class and its tests in one go.

When is plain sorting enough?

If you have dozens of items and sort once — just sort, it's simpler. A heap pays off when items keep coming and going and you always need the single most important one.

Is this heap the same as the memory "heap"?

No, it's a coincidence of names. The heap as the memory area where a program's objects live has nothing to do with this data structure.