complexity of heap data structure

Question

I'm trying to count running time of build heap in heap sort algorithm

BUILD-HEAP(A) 
heapsize := size(A); 
  for i := floor(heapsize/2) downto 1 
    do HEAPIFY(A, i); 
  end for 
END 

The basic idea behind why the time is linear is due to the fact that the time complexity of heapify depends on where it is within the heap. It takes O(1) time when the node is a leaf node (which makes up at least half of the nodes) and O(logn) time when it’s at the root.

The O(n) time can be proven by solving the following:

image by HostMath

what I understand here O(h) means worst case for heapify for each node, so height=ln n if the node is in the root for example to heapify node 2,1,3 it takes ln_2 3 =1.5 the height of root node 2 is 1, so the call to HEAPIFY is ln_2 n=height = O(h)

BUILD-HEAP(A) 
heapsize := size(A); 
  for i := floor(heapsize/2) downto 1 
    do HEAPIFY(A, i); 
  end for 
END 




 suppose this is the tree

       4    .. height2
      / \ 
    2   6  .. height 1
    /\   /\  
  1 3 5 7  .. height 0

A quick look over the above algorithm suggests that the running time is O(nlg(n)), since each call to Heapify costs O(lg(n)) and Build-Heap makes O(n) such calls. This upper bound, though correct, is not asymptotically tight. the Time complexity for Building a Binary Heap is O(n).

im trying to understand, the heapsize/2 means for loop only call HEAPIFY heapsize/2 times. in tree above, heapsize=7, 7/2= 3 so root will be {1,2,6} so n/2

and every call to HEAPIFY will call HEAPIFY again until reach the last leaf of every root, for example 2 will call heapify 1 times, 6 will call heapify 1 times, and 1 will call heapify 2 times. so it is the height of the tree which is ln n. am i right?

then the compelxity will be O(n/2 * ln n) = O(n ln n)

which one is right? O(n ln n) or O(n)?

and how can i get O(n)?

im reading this as reference , please correct me if im wrong thanks! https://www.growingwiththeweb.com/data-structures/binary-heap/build-heap-proof/ this is the reference i used, and also i read about this in CLRS book

https://www.hostmath.com/Show.aspx?Code=ln_2%203

Answer 1

The complexity is O(n) here is why. Let's assume that the tree has n nodes. Since a heap is a nearly complete binary tree (according to CLRS), the second half of nodes are all leaves; so, there is no need to heapify them. Now for the remaining half. We start from node at position n/2 and go backwards. In heapifying, a node can only move downwards so, as you mentioned, it takes at most as much as the height of the node swap operations to complete the heapify for that node.

With n nodes, we have at most log n levels, where level 0 has the root and level 1 has at most 2 nodes and so on:

level 0:              x
.                    / \  
level 1:            x   x
.
level log n:    x x x x x x x x 

So, we have the following:

All nodes at level logn-1 need at most 1 swap for being heapified. (at most n/2 nodes here)

All nodes at level logn-2 need at most 2 swaps for being heapified. (at most n/4 nodes here)

....

All nodes at level 0 need at most logn swaps for being heapified. (at most 1 node here, i.e, the root)

So, the sum can be written as follows:

(1 x n/2 + 2 x n/4 + 3 x n/8 + ... + log n x n/2^logn)

Let's factor out n, we get:

n x (1/2 + 2/4 + 3/8 + ... + log n/2^logn)

Now the sum (1/2 + 2/4 + 3/8 + ... + log n/2^logn) is always <= 2 (see Sigma i over 2^i); therefore, the aforementioned sum we're interested in is always <= 2 x n. So, the complexity is O(n).