liveBook · Manning

Heapify

As explained in The Coder Cafe

Heapify is the process of rearranging elements to restore the heap property after an update or during heap construction.

Heapify rearranges a heap’s array representation to restore the min-heap or max-heap property after an update or during construction. section 1.2

Heapify has two common directions:

  • Heapify up compares a newly inserted element with its parent and swaps them when the heap property is violated. section 1.2
  • Heapify down compares a violating element with its smallest child in a min-heap, or largest child in a max-heap, and swaps as needed. section 1.2
  • Building a heap from an unsorted array uses heapify down and costs O(n), rather than inserting each element individually at O(n log n). section 1.2

Repairing after insertion

When an element is inserted, compare it with its parent. If it violates the min-heap or max-heap property, swap upward and continue until the property is restored. section 1.2

How The Coder Cafe covers it

How deep it goes
Explains upward and downward repair plus construction costs, but does not provide implementation code.
Examples
Uses parent-child swaps after insertion and smallest-or-largest-child swaps after extraction or during construction.
What it assumes
Assumes familiarity with heap properties, parent-child array indexing, and min-heaps or max-heaps.
What you can do after
Apply heapify to understand why heap insertion and extraction take O(log n) rather than O(1).
How it connects
Connects heapify with binary heaps, priority queues, arrays, insertion, extraction, and heap construction.

Also explained in

Compare how 3 books explain heapify →

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.