How can build heap be done in linear time? — A tree of size n nodes, will have floor(n/2^h) nodes with height >= h. The last half of nodes will be leaves, so they already satisfy the heap property. No work needs to be done on them. going bottom-up (ignoring the last n/2 items) and satisfying the heap property one level at a time, each level going up the tree has to do at most 1 operation more than the level below it. But as you go up the tree, higher levels have fewer nodes, so you may be doing more operations, but it happens on fewer number of times. This resembles a series: n/2 - height 1: 1 operations n/4 - height 2: 2 operation n/8 - height 3: 3 operations ... going to floor(n/2^h) - height h: h operations n * (1/2 + 2/4 + 3/8 + 4/16 ....) = n * 1 = n