Notice that in the first method (insert one-by-one), in the worst case the nodes that are initially inserted at the last level might have to bubble up all the way to the top. There are `O(n/2)` nodes which may need to bubble up `O(\lg n)` levels, hence the complexity is at least `O(n \lg n)`.
On the other hand for the heapify method, the nodes bubble down. The majority of the nodes are near the bottom and the number of level they can bubble down is small, while nodes near the top have to move further there is much less of them. All in all, the maximum number of comparisons is `O(n)`
Cecilia R. Aragon and Raimund Seidel developed the Treap data structure in 1989. It is known that for a random insert order, the resulting binary tree is expected to have height `O(\lg n)`. By assigning each new node with a random priority value and rotating the nodes to satisfy the heap property on the priority value it can be shown that the resulting tree is similar to one constructed by inserting the nodes in random order.