Heap vs Sorted Array for Priority Handling

Data structures · Priority queues · Performance

An emergency room does not treat patients in the order they walk in. A nurse looks at each person and the sickest one goes first. Software has the same problem everywhere: tasks, packets, alerts and routes all arrive with different levels of urgency, and something has to hand you the most urgent one, fast. There are two classic ways to build that. One keeps everything sorted. The other keeps everything “sorted enough.” This article shows you, with real numbers, when each one wins.

The problem: always give me the most urgent thing

I have been writing and reviewing code for a little over fifteen years, and the same question comes back every couple of years in a new costume. A job scheduler needs the next job to run. A game server needs the next event to fire. A routing service needs the next closest intersection. Different industries, same shape: items arrive in any order, each carries a priority, and at any moment somebody asks for the single most important item.

The abstract name for this is a priority queue. It is a queue where the order of leaving is decided by priority, not by arrival. You need exactly three operations, and almost nothing else.

The three operations that matter

• insert(item, priority) adds a new item.
• peek() shows the most urgent item without removing it.
• extract() removes and returns the most urgent item.

That is the whole contract. How you store the items behind the scenes is your business, and the storage choice decides how fast each of those three runs. In this article, “most urgent” is just whichever end of the ordering you care about. Python’s standard library treats the smallest number as most urgent, so I will use that convention for the heap. For the sorted array I will keep the list in ascending order and call the highest number most urgent, which keeps removal cheap. The two structures can be flipped either way, and the cost is the same.

Where priority handling shows up in real life

Before we compare structures, it helps to see how often this pattern appears. Here are the ones I run into most.

• Hospital triage. A broken wrist waits, chest pain does not.
• Task and job schedulers. Run the highest-priority job whose time has come.
• Shortest-path routing. Dijkstra’s algorithm repeatedly asks for the closest unvisited place.
• Top-K tracking. Keep the ten best scores out of a stream of millions.
• Event simulation and timers. Always fire the event with the earliest timestamp next.
• Merging sorted logs. Pull the smallest head item from many sorted files.

We will return to each of these in the interactive panel later. For now, hold on to the hospital, because it makes the data-structure question concrete.

Why a plain queue or an unsorted list is not enough

Start with the two ideas everybody tries first.

Attempt 1: a normal queue

A normal queue serves first come, first served. That is fair at a bakery and a disaster at a hospital. The chest-pain patient who arrived last would wait behind everyone with a sprained ankle. A plain queue ignores priority entirely, so it cannot be the answer.

Attempt 2: an unsorted list

Throw items into a list in any order. Insertion is instant, you just append. But to find the most urgent item you have to scan the whole list, which costs O(n). With ten items that is nothing. With a million items and a million requests, you are doing about a trillion comparisons. The unsorted list moves all the cost to the extraction side.

So the real design question is where to spend your effort: at insertion time, at extraction time, or a little at each. That is exactly the difference between our two contenders.

Contender one: the sorted array

The idea is simple enough to explain to anyone. Keep the array sorted at all times. If the most urgent item is at one end, extraction is trivial. If you keep the array ascending and treat the largest as most urgent, the best item sits at the last position, and removing the last element of an array costs O(1). Peeking costs O(1) too.

Insertion is where you pay. To add a new item, you first find where it belongs. Because the array is sorted, you can use binary search and find the spot in O(log n) comparisons. That part is cheap. The expensive part is that everything after that spot has to slide one position to the right to make room. On average that is half the array.

Here is the whole thing in Python. It uses the bisect module, which does the binary search and the insertion for you.

from bisect import insort

class SortedPQ:
    """Highest number = most urgent. Kept in ascending order,
    so the most urgent item is always at the end of the list."""
    def __init__(self):
        self.a = []

    def push(self, x):
        insort(self.a, x)                 # binary search + shift: O(n)

    def pop(self):
        return self.a.pop()               # remove from the end: O(1)

    def peek(self):
        return self.a[-1]

That is nearly all of it. The simplicity is a real virtue, and I do not want to understate it. A sorted array is cache-friendly, easy to debug, easy to print, and the memory move that does the shifting is one of the most heavily optimised operations a computer knows. We will come back to that, because it changes the verdict for small data.

Contender two: the binary heap

A heap makes a different bargain. It refuses to keep everything sorted. It only promises one thing: every parent is at least as urgent as its children. That single rule guarantees the most urgent item is at the top, and it is much cheaper to maintain than a full ordering.

The clever part is how it is stored. A heap is conceptually a tree, but it lives in a plain array with no pointers at all. The tree is kept complete, filled level by level from left to right, so the position of every relative is just arithmetic:

• The parent of index i is at (i - 1) // 2.
• The children of index i are at 2i + 1 and 2i + 2.
• The root, the most urgent item, is at index 0.

Here is what happens if you insert 5, 3, 8, 1, 9 and 2 into a min-heap, one at a time. The array and the tree below are the same data seen two ways.

Notice that the array [1, 3, 2, 5, 9, 8] is not sorted. The 3 sits before the 2. A heap does not care. It only cares that the 1 at the top is the smallest and that each parent beats its children.

Inserting: sift up

To add an item, append it at the end of the array, which is the next free slot in the tree. Then compare it with its parent. If it is more urgent, swap them. Repeat until it is in a good place or reaches the root. The tree has about log₂(n) levels, so you do at most that many swaps. A million items means roughly twenty levels, not a million moves.

Removing: sift down

The top item is the one you want. Take it out, which leaves a hole at the root. Fill the hole by moving the last array element to the root, then let it sink: compare it with its two children, swap with the more urgent child, and repeat. Again at most about log₂(n) swaps.

The full implementation is short enough to read in one sitting. I wrote it by hand so you can see the mechanics, though in real projects you would reach for a library.

class MinHeap:
    def __init__(self):
        self.a = []                       # the heap lives in a plain list

    def push(self, x):
        a = self.a
        a.append(x)                       # 1. put it at the end
        i = len(a) - 1
        while i > 0:                      # 2. sift up while smaller than parent
            parent = (i - 1) // 2
            if a[i] >= a[parent]:
                break
            a[i], a[parent] = a[parent], a[i]
            i = parent

    def pop(self):
        a = self.a
        top = a[0]
        last = a.pop()                    # 1. remove the last item
        if a:
            a[0] = last                   # 2. move it to the root
            i, n = 0, len(a)
            while True:                   # 3. sift down
                left, right, small = 2 * i + 1, 2 * i + 2, i
                if left < n and a[left] < a[small]:
                    small = left
                if right < n and a[right] < a[small]:
                    small = right
                if small == i:
                    break
                a[i], a[small] = a[small], a[i]
                i = small
        return top

    def peek(self):
        return self.a[0]

Python ships the same idea in the heapq module, which operates on an ordinary list. Here it is running a small emergency-room queue, where a lower number means a sicker patient.

import heapq
from itertools import count

queue, tie = [], count()                  # tie-breaker keeps arrival order

def add(priority, name):
    heapq.heappush(queue, (priority, next(tie), name))

add(3, "Ana")
add(5, "Ben")
add(2, "Chi")
add(2, "Dev")
add(1, "Eli")

while queue:
    priority, _, name = heapq.heappop(queue)
    print(priority, name)

The output is, in order: Eli (1), Chi (2), Dev (2), Ana (3), Ben (5). Chi and Dev share priority 2 and come out in the order they arrived, thanks to the little counter in the tuple. That detail matters in production, and I will say more about it in the pitfalls section.

The complexity table

Here is how the common ways of building a priority queue compare. N is the number of items stored.

Read the table by asking which column your program hammers. If you insert once and then extract a million times, the sorted array looks great. If you interleave inserts and extracts all day, the heap’s O(log n) on both sides is the safer bet.

Counting the actual work

Big-O is a promise about growth, not a stopwatch. So I measured. In the experiment below, I generated n random priorities, inserted all of them, and then extracted everything. Instead of timing, I first counted the elementary moves, because counts are the same on every machine.

At a hundred thousand items, the sorted array shuffled about 2.5 billion elements while the heap made around 1.5 million swaps. That is a gap of roughly 1,600 times. Notice how the sorted array’s cost grows about a hundredfold every time n grows tenfold. That is the quadratic growth you would expect from n inserts that each cost O(n). The heap’s cost grows only a little faster than n itself.

Now the stopwatch, and an honest surprise

Counts are tidy, but you pay in seconds. I timed the same insert-everything-then-extract-everything test using the sorted array above against Python’s heapq. Timings depend on the machine, so treat the shape as the lesson and not the exact digits.

The gap opens exactly as theory says. At 100,000 items the sorted array needed about a second and the heap about 0.04 seconds. But look at the small end. At a thousand items both finish in well under a millisecond, and that points to something that surprises many people.

The reason is that shifting elements in a Python list is not a Python loop. It is a single memory-move operation written in C, and modern processors copy contiguous memory astonishingly fast. A heap, on the other hand, does a lot of small comparisons and swaps with a fair amount of overhead per step. When n is small, a very fast O(n) move can beat a slower O(log n) procedure.

To test this properly I ran a second experiment that looks more like a real service: a queue that stays at a steady size while 50,000 insert-then-extract pairs flow through it.

This is the part I most want you to take away. For queues holding a hundred or a thousand items, the sorted array was actually a little faster in my run. By ten thousand items the heap was already about twice as fast, and at a hundred thousand it was nearly thirty times faster. The crossover point depends on your language and hardware, but it is real, and it is usually somewhere in the low thousands.

The same idea in five real settings

Click a tab below to see how priority handling looks in different places. No page reload, nothing to install.

How to choose: a decision table

Building a heap in one go: heapify

There is a trick worth knowing. If you already have all n items, you do not need to insert them one by one, which would cost O(n log n). Python’s heapq.heapify(list) rearranges the list in place into a valid heap in O(n) time. It works by sifting down every non-leaf node, starting from the bottom, and the maths happens to add up to linear time because most nodes sit near the bottom where there is almost nothing to sift.

The practical rule: when you have the data up front, heapify. When it arrives over time, push one at a time. And if you are going to sort everything anyway, a plain sort is simpler still.

Pitfalls I have seen in production

1. Python’s heapq is a min-heap only

If you want the largest item first, negate the priorities when you push and negate them again when you pop. Forgetting this is a classic source of “why is my queue upside down?” bugs. Java’s PriorityQueue is also a min-heap by default, while C++’s std::priority_queue is a max-heap by default. The defaults differ across languages, so check before you trust.

2. Equal priorities have no guaranteed order

A heap is not stable. Two items with the same priority can come out in either order. If fairness matters, and in a job queue it nearly always does, add a tie-breaker such as an incrementing counter, as we did in the tuple earlier. Also be aware that if your items are not comparable (two dictionaries, say), Python raises an error when priorities tie. The counter in the middle of the tuple prevents that comparison from ever reaching the payload.

3. There is no cheap way to change a priority

Say a task becomes more urgent after it is queued. Finding an arbitrary item inside a heap takes O(n), because the heap only organises the top. The common workaround, used in Dijkstra implementations everywhere, is lazy deletion: push a new entry with the better priority, and when you pop a stale entry later, notice it is outdated and skip it.

4. A heap is not sorted

Printing the underlying list gives you something that looks almost sorted, which tempts people to iterate over it directly. Do not. The only guaranteed position is index 0. To get everything in order you must pop repeatedly, or just sort a copy.

5. Thread safety is on you

Neither structure is safe for concurrent writers. Wrap access in a lock, or use a purpose-built concurrent queue such as Python’s queue.PriorityQueue, which is a heap plus locking.

What the standard libraries give you

You will rarely write a heap by hand outside of an interview or a learning exercise. Python gives you heapq for lists and queue.PriorityQueue for threads. Java gives you PriorityQueue. C++ gives you std::priority_queue. JavaScript has no built-in priority queue, so people either write a small heap or pull in a package. All of these are heaps underneath. For a sorted array in Python, bisect is the standard tool, and the third-party sortedcontainers package offers a sorted list with much better insertion behaviour for large sizes.

Common mistakes when comparing the two

• Benchmarking only big inputs. You will miss the small-n region where the simple option wins.
• Benchmarking only small inputs. Your prototype works fine and then collapses on production data.
• Forgetting the workload mix. Insert-heavy, extract-heavy and balanced workloads can favour different structures.
• Using sort() in a loop. Re-sorting after every insertion is O(n log n) per insert. Insert with bisect or use a heap instead.
• Ignoring the tie rule. Equal priorities need a decision, not a surprise.

Test yourself

Tap a question to reveal the answer. The correct option is marked.

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

1. Indexes 1 and 2
2. Indexes 3 and 4
3. Indexes 5 and 6
4. Index 4 only

Children of index i are at 2i + 1 and 2i + 2. For i = 2 that gives 5 and 6.

Why is inserting into a sorted array O(n) even though binary search is O(log n)?

1. Binary search is actually O(n)
2. Later elements must shift to make room
3. The array must be re-sorted afterwards
4. Arrays cannot grow

Binary search only finds the slot. Opening a gap there requires moving, on average, half the array.

You push two tasks with equal priority into heapq as plain (priority, task) tuples and the tasks cannot be compared. What can happen?

1. A TypeError when the priorities tie
2. The first task is silently dropped
3. They are sorted alphabetically
4. Nothing, it always works

On a tie Python compares the next tuple element. If that is not comparable, it raises an error. A counter in the middle prevents it and keeps FIFO order.

Which situation most favours a sorted array over a heap?

1. Millions of mixed inserts and extracts
2. Dijkstra on a huge graph
3. A scheduler with a growing backlog
4. A small collection you also need to read in sorted order or by rank

A sorted array gives instant sorted iteration, ranks and both ends. A heap only guarantees its top item.

What is the time complexity of building a heap from n existing items with heapify?

1. O(n log n)
2. O(log n)
3. O(n)
4. O(n squared)

Most nodes are near the bottom and barely move, so the total work adds up to linear time.

Frequently asked questions

What is a priority queue?

A queue where items leave in order of priority instead of arrival time. It supports insert, peek and extract, and can be built on a heap, a sorted array or other structures.

Is a heap the same as a sorted array?

No. A heap only guarantees that each parent is at least as urgent as its children, so the top item is correct but the rest is only partly ordered. A sorted array is fully ordered.

Why does Python only offer a min-heap?

It is a design choice for simplicity. For a max-heap, negate numeric priorities when pushing and negate again after popping, or wrap items in a class with reversed comparison.

Is heapsort related to this?

Yes. Heapsort builds a heap and then extracts the top item repeatedly, which gives an O(n log n) sort that works in place.

When should I use sortedcontainers instead of bisect?

When the list can grow large and you insert often. Its SortedList avoids the full-array shifting of a plain list and stays fast at sizes where bisect.insort becomes slow.

Can a heap find an arbitrary item quickly?

No. Searching a heap is O(n) because only the top is organised. If you need lookups by key as well as priority, pair the heap with a dictionary or use an indexed priority queue.