liveBook · Manning

Min-heap

As explained in The Coder Cafe

A min-heap is a binary heap in which every parent node is smaller than its children.

A min-heap is a complete binary tree where every parent is smaller than its children. It provides quick access to the minimum element and commonly implements priority queues. section 1.2

Core operations balance fast minimum access with logarithmic updates:

  • isEmpty checks whether the heap contains elements. section 1.2
  • insert adds an element and restores order with heapify up in O(log n). section 1.2
  • getMin returns the minimum without removing it in O(1). section 1.2
  • extractMin removes and returns the minimum, then uses heapify down in O(log n). section 1.2

Array representation

When a heap is stored in an array, an element at index i has children at 2i + 1 and 2i + 2, and its parent at (i - 1) / 2. Building a heap from an unsorted array takes O(n). section 1.2

How The Coder Cafe covers it

How deep it goes
Defines tree and array structure, operations, heapification, index formulas, and asymptotic costs.
Examples
Uses array positions, child-parent index calculations, and a contrasting max-heap representation.
What you can do after
Apply it by implementing minimum-oriented priority queues with logarithmic insertion and extraction.
How it connects
Links binary trees, arrays, priority queues, heapify up, and heapify down.

Also explained in

Compare how 3 books explain min-heap →

Related concepts

This explainer was generated by Manning's knowledge graph from the text of The Coder Cafe. The section links point to the parts of the book it draws on.