Growing with the Web

Binary heap: Build heap proof


The binary heap data structure supports a build heap operation that runs in O(n). Intuitively it might seem that it should run in O(n \log n) time since it performs an O(\log n) operation n/2 times. This article provides a proof of the linear run time.


comments powered by Disqus
Like this article?
Subscribe for more!