Sign in to watch this lesson
Algorithms - Linear Data Structures · 5:13
Binary Heaps and priority_queue
A binary heap is an array read as a tree: the children of index i sit at 2i+1 and 2i+2, and every parent is no larger than its children. We push 5, 3, 8, 1, 9, 2 with sift-up to get [1, 3, 2, 5, 9, 8], pop with sift-down to get [2, 3, 8, 5, 9], see why std::priority_queue is a max-heap by default, and measure bottom-up heapify against one push at a time on this Mac. Then two patterns: top-k with a size-k min-heap, and a first look at the running median with two heaps.
You will learn
- Map a binary heap between its array and its tree (children 2i+1 and 2i+2, parent (i-1)/2) and state the heap property
- Implement push (sift-up) and pop (sift-down, swapping with the smaller child) in O(log n), and explain why heapify is O(n)
- Use std::priority_queue correctly: max-heap by default, greater<> for a min-heap, and the 'lower priority' meaning of a custom comparator
- Apply heaps to top-k selection (size-k min-heap, O(n log k)), lazy deletion, and the running median with two balanced heaps