Wrote up a proof for binary heap's build heap linear time complexity on the weekend, tried to focus on simplicity
The binary heap data structure supports a build heap operation that runs in O(n). Intuitively it would seem that it should run in O(n \log n) time however, since it runs an O(\log n) operation n/2 times. This article provides a proof of the linear run time.
Add a comment...