Heap

What it is

A heap is a structure designed for fast access to the smallest or largest item.

It does not keep everything fully sorted.

It keeps the top cheap to retrieve.

When to use it

A heap usually fits when the problem asks for:

• the smallest or largest item repeatedly
• top-k
• priority ordering

If you only care about the next most important item, sorting everything may be too much work.

Common mistake

The classic mistake is thinking of a heap as “a weird array.”

The point is not the representation.

The point is the cheap top operation.

Better question

Before applying it, ask:

1. do I need the whole set fully sorted?
2. or do I only need the next min/max item many times?
3. does a priority queue describe the problem better?