Heaps vs. Ordered Arrays

Now that you know the efficiency of heaps, let’s see why it’s a great choice for implementing priority queues.

Here’s a side-by-side comparison of ordered arrays versus heaps:

At first glance, it seems that it’s a wash. Ordered arrays are slower than heaps when it comes to insertion but faster than heaps for deletion.

However, heaps are considered to be the better choice, and here’s why.

While O(1) is extremely fast, O(log N) is still very fast. And O(N), by comparison, is slow. With this in mind, we can rewrite the earlier table this way:

In this light, it becomes clearer as to why the heap is considered the better choice. We’d rather use a data structure that is consistently very fast than a data structure that is sometimes extremely fast and sometimes slow.

It’s worth pointing out that priority queues generally perform insertions and deletions in about equal proportion. Think about the emergency room example, where we expect to treat everyone who comes in. So we want both our insertions and deletions to be fast. If either operation is slow, our priority queue will be inefficient.

With a heap, then, we ensure that both of the priority queue’s primary operations—insertion and deletion—perform at a very fast clip.