CS 61B › Lectures
Lecture 14: Heaps
- A binary heap is a complete binary tree stored in an array.
- In a min-heap, every parent is less than or equal to its children.
- With the array starting at index 1, the children of k sit at 2k and 2k + 1, and the parent of k sits at k / 2.
- Insert puts the new item at the end and swims it up; removing the minimum moves the last item to the top and sinks it down.
- Both operations take O(log n) time, because the tree's height is log n.









