Find the 3rd largest of 9 values with a min heap that never holds more than 3. Once it is full, its root is the 3rd largest seen so far.
Finding the 3rd largest value using a min heap of size 3. The values are 3, 2, 1, 5, 6, 4, 9, 7, 8.
3 goes in: the heap holds 0 of 3, so everything is kept.
3 is added to the heap, which now holds 1 of 3.
2 goes in: the heap holds 1 of 3, so everything is kept and 2 climbs to its level.
2 is added to the heap, which now holds 2 of 3.
1 goes in: the heap holds 2 of 3, so everything is kept and 1 climbs to its level. The heap is full now, and its root 1 is the 3rd largest so far.
1 is added to the heap, which now holds 3 of 3. The root 1 is the 3rd largest so far.
5 is larger than the root 1, so 1 can no longer be in the top 3. 1 leaves, 5 takes the root and sinks to its level. The new root 2 is the 3rd largest so far.
5 replaces the root 1 and sinks. The root is now 2.
6 is larger than the root 2, so 2 can no longer be in the top 3. 2 leaves, 6 takes the root and sinks to its level. The new root 3 is the 3rd largest so far.
6 replaces the root 2 and sinks. The root is now 3.
4 is larger than the root 3, so 3 can no longer be in the top 3. 3 leaves, 4 takes the root and sinks to its level. The new root 4 is the 3rd largest so far.
4 replaces the root 3 and sinks. The root is now 4.
9 is larger than the root 4, so 4 can no longer be in the top 3. 4 leaves, 9 takes the root and sinks to its level. The new root 5 is the 3rd largest so far.
9 replaces the root 4 and sinks. The root is now 5.
7 is larger than the root 5, so 5 can no longer be in the top 3. 5 leaves, 7 takes the root and sinks to its level. The new root 6 is the 3rd largest so far.
7 replaces the root 5 and sinks. The root is now 6.
8 is larger than the root 6, so 6 can no longer be in the top 3. 6 leaves, 8 takes the root and sinks to its level. The new root 7 is the 3rd largest so far.
8 replaces the root 6 and sinks. The root is now 7.
The 3rd largest is 7, the root. 0 values bounced off the root and 6 replacements sank in, each O(log k), so O(n log k) with only k values in memory.
The 3rd largest value is 7. 0 values were dropped and 6 replaced the root.