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
- binary heap — A complete binary tree stored in an array in which every parent is ordered before its children, so the smallest (or largest) item is always at the root.
- sift-up and sift-down — The two heap repair operations: sift-up moves a new item up past larger parents, and sift-down moves a displaced root down past smaller children.
- heapq — Python's standard-library module of functions that treat an ordinary list as a binary min-heap.
Taught in
- Heaps And Priority Queues — Algorithms & Data Structures for Working Engineers