Skip to content
BENIBIX Learn

Heap (Data Structure)

Development🧮 Algorithms & Data StructuresData Structures

Also known as Heap, Min-Heap, Max-Heap, Priority Queue

A tree that keeps the smallest item on top, or the largest.

Think of it like

Think of it like a doctor's waiting room. The sickest person goes next.

Example

Jack's task runner keeps jobs in a heap by urgency. Whatever is most urgent comes out next, even if it arrived last.

Why it matters

Heaps pick the next job in task lists. Map apps use them to find short routes too.

Definition

A heap is a tree that always keeps the smallest item at the top, or the largest in a max-heap. It does not keep everything in order, only enough to find the top item at once. Taking the top item out and adding a new one each take about log n steps. That makes it the usual way to build a priority queue. Python's heapq module gives you one on a plain list.

Example code

python
>>> import heapq
>>> h = [5, 1, 8]
>>> heapq.heapify(h)
>>> heapq.heappop(h)
1
The smallest number always comes out first.

Common mistake

Mixing up this heap with the heap in memory. They share a name and nothing else.

Key takeaways

  1. 1
    Top item first. Smallest or largest.
  2. 2
    Partly sorted. Just enough for the top.
  3. 3
    A priority queue. Its most common use.

Compare