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.
In more detail
After an append, sift-up swaps with the parent until the heap property holds. After the root is removed and replaced by the last item, sift-down swaps with the smaller child until it holds. Each walks one root-to-leaf path, so each costs O(log n).
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.
- heap property — The rule that every parent in a heap is ordered before its children: no larger than them in a min-heap.
- heapify — Rearranging an unordered list into a valid heap in place, which Python's heapq.heapify does in linear time.
Taught in
- Heaps And Priority Queues — Algorithms & Data Structures for Working Engineers