# Binary heap: Build heap proof

Published

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.

## Textbooks

Here are two CS textbooks I personally recommend; the Algorithm Design Manual (Steven S. Skiena) is a fantastic introduction to data structures and algorithms without getting to deep into the maths side of things, and Introduction to Algorithms (CLRS) which provides a much deeper, math heavy look.