Skip to content

Heaps and Priority Queues

A binary min-heap is a complete binary tree satisfying:

key(parent) <= key(child)

Completeness permits a compact array representation. For zero-based index i:

  • parent: (i - 1) / 2 for i > 0;
  • left child: 2i + 1;
  • right child: 2i + 2.

Operations

Operation Binary heap
Inspect minimum Θ(1)
Insert O(log n)
Remove minimum O(log n)
Build from n items Θ(n)
Find arbitrary value Θ(n)

Bottom-up construction is linear because most nodes are near the leaves and move only a short distance. Multiplying n nodes by log n gives a valid but loose upper bound.

Java

Queue<Integer> priorities = new PriorityQueue<>();
priorities.add(8);
priorities.add(3);
priorities.add(5);
int smallest = priorities.remove(); // 3

Iteration over a PriorityQueue is not guaranteed to produce sorted order; only head operations follow the priority contract.

Exercises

  1. Restore the heap after removing the root.
  2. Derive a max-heap comparator without integer subtraction overflow.
  3. Explain why a heap is not an efficient general search structure.