heapify

Rearranging an unordered list into a valid heap in place, which Python's heapq.heapify does in linear time.

In more detail

Sifting down every non-leaf node from the bottom up builds a heap in O(n), faster than n separate pushes at O(n log n). It is the first step of heap sort.

Related terms

Taught in

References