liveBook · Manning

Max heap

As explained in The Coder Cafe

A max-heap is a binary heap in which every parent node is larger than its children.

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

A max heap supports these operations:

  • isEmpty checks whether the heap contains elements. section 1.2
  • insert adds an element and restores ordering with heapify up; it costs O(log n). section 1.2
  • getMax returns the maximum without removing it in O(1). section 1.2
  • extractMax removes and returns the maximum, then uses heapify down in O(log n). section 1.2
  • Building a heap from an unsorted array costs O(n), rather than repeatedly inserting elements. section 1.2

Array representation

Heaps are usually stored in arrays. For a node at index i, the left child is 2i + 1, the right child is 2i + 2, and the parent is (i - 1) / 2. Thus, a value such as 39 at index 1 has children at indices 3 and 4 and a parent at index 0. section 1.2

How The Coder Cafe covers it

How deep it goes
Defines completeness, heap ordering, array indexing, operations, and costs; stops short of implementation detail beyond heapify directions.
Examples
Uses 39 at array index 1 to demonstrate child and parent calculations.
What you can do after
Evaluate maximum-priority access, choose a max-heap over a min-heap, and estimate operation costs.
How it connects
Connects binary trees, arrays, priority queues, min-heaps, and heapify operations.

Also explained in

Compare how 2 books explain max 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.