Heap (Min / Max)

A heap is a tree‑based data structure that implements a priority queue:

• In a min‑heap, the smallest element is always at the root.
• In a max‑heap, the largest element is always at the root.

Heaps are usually implemented as arrays representing a complete binary tree.

Heap Properties

Two key properties:

• Shape property:
  • The tree is complete: all levels are filled from left to right, except possibly the last.
• Heap property:
  • Min‑heap: each node’s key is ≤ its children’s keys.
  • Max‑heap: each node’s key is ≥ its children’s keys.

Because of the shape property, we can store the tree in an array:

• Node at index i.
• Left child: 2 * i + 1.
• Right child: 2 * i + 2.

Core Operations and Complexity

For n elements:

Operation	Description	Time
insert(x)	Add new element	O(log n)
getMin / getMax	Peek top element	O(1)
extractMin / extractMax	Remove and return top	O(log n)
buildHeap	Heapify an array	O(n)

Internally:

• Insertion uses sift up (bubble up).
• Extraction uses sift down (heapify from root).

Heaps in Practice

Heaps are a natural fit for:

• Priority queues:
  • Process tasks in order of priority.
  • Schedule jobs, timer events, or background work.
• Top‑K queries:
  • Maintain a heap of size k to track best k elements seen so far.
• Graph algorithms:
  • Dijkstra’s algorithm uses a min‑heap to pick the next closest node.
• Event simulation / scheduling:
  • Handle events in order of time or priority.

Many languages provide a heap or priority queue in the standard library:

• Java: PriorityQueue<E>.
• Python: heapq.

These are usually min‑heaps; max‑heap behavior can be emulated by negating keys or using custom comparators.

Min‑Heap vs Max‑Heap

Conceptually identical except for comparison:

• Min‑heap:
  • Root is the smallest element.
  • Good for tasks like “always process the closest deadline first”.
• Max‑heap:
  • Root is the largest element.
  • Good for tasks like “always process the most expensive task first”.

Many problems can be solved symmetrically with either, just by flipping the comparator.

Relation to Other Structures

Heaps vs:

• Sorted array/list:
  • Sorted array gives fast binary search but slow insert.
  • Heap gives fast “get top” and insert, but no general O(log n) search by key.
• Balanced BST:
  • BST supports O(log n) search by key and in‑order traversal.
  • Heap only supports efficient access to the top element.

Heaps are ideal when you frequently need the current best element, not arbitrary searches. For interview patterns and code, see [Heap Fundamentals](/blog/algorithms/heap-top-k/heap-fundamentals) and [Top K Problems](/blog/algorithms/heap-top-k/top-k-problems).