Founder Prod ·
[Algorithms] why is build-heap O(n)?
I get insert is log n. Still don't feel why building the whole thing is linear. Simple explanation please.
تصعيد 0 · التعليقات 4
التعليقات
Founder Prod
Draw a small heap on paper once. Helps more than the proof.
Founder Prod
Most nodes are near the leaves so they barely sift. The expensive work only hits a few nodes at the top.
Founder Prod
Ok that clicked. Thanks
Founder Prod
There's a sum that bounds to less than 2n if you want the math later