Core · Module 11 · Lesson 2 of 4
Sift-up and sift-down
A heap inserts by appending at the end and swapping upward, and removes the minimum by moving the last item to the root and swapping downward. Each walks one path, so both are O(log n).
By the end you can
- Insert into a heap by appending and sifting up
- Remove the minimum by moving the last element to the root and sifting down toward the smaller child
- Explain why both keep the heap property, and handle ties, max-heaps and priority updates
Builds on The heap property in an array.
01 · A question first
A new patient joins the heap at the very end of the array, however urgent they are. How does a critical patient reach the front in a handful of swaps, and how does the heap refill the front after the most urgent patient leaves?
Make a guess before you read on.
02 · The idea
Members only
Unlock the full lesson
This lesson is part of the membership. Join to read it in full, along with every other premium deep dive.
What's inside
- Two rules, two repairs
- Push: append, then sift up
- Pop: move the last to the root, then sift down
- Peek, replace and push-pop
- Ties and priorities
- Changing a priority
- Max-heaps
- Pseudocode & Multi-Language Implementations (C++, Java, Python)
03 · Practice
Asked in interviews
Something wrong with this lesson? Report a problem