complexity of build heap in heap sort

[surfersss]

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 

suppose this is the tree

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

it is said 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 {4,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?
im sorry its log n based 2
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)?


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

[jonnin]

of the tree which is ln n. am i right?

a balanced, binary tree has height near the lg of n (not LN, that is e based). Its close enough to say lg(n) in big-o terms, but its not exact unless all leaves are filled.

a linked list is a degenerate unbalanced binary tree. That is not important today, but its a warning to not memorize things and to look critically at the algorithm. this one keeps it balanced, I believe.

[JLBorges]

> so it is the height of the tree which is ln n. am i right?

No. n is the size of (the number of nodes in) the heap.

The optimal algorithm has O(n) complexity.
This picture may help understand why it is O(n) https://stackoverflow.com/a/54972825

[Duthomhas]

On my phone; lost a better answer, so this stupidly-short answer will have to do for now.

Ignore that Geeks-for-Geeks stuff; they regularly present garbage for fact. Plus, you have misread it anyway, but honestly, I dont blame you for being confused by them.

Heapsort IS asymptotically tight, both on the upper AND lower bounds, and is one of the best-performing sorts available.

The entire make-heap process (also called heapify) takes (n log n) time, because each sink/push-down (which you are calling heapify) takes (log n) [by definition of a binary tree] and you must perform n/2 sinks. Hence: n log n (remember, constants get dropped).

Once the heap is made, we must simply maintain it for each step in sorting. Again we perform n push-downs, making the sorting part n log n.

Together that is 2n log n, which asymptotically is just n log n (remember, ignore constants).

For more, like visuals (GIFs), google cplusplus.com FAQ heapsort.

Hope this helps.

[JLBorges]

Optimal make heap has O(n) complexity.

The C++ standard specifies that he complexity of std::make_heap is: "at most 3*(last-first) comparisons".
https://en.cppreference.com/w/cpp/algorithm/make_heap

[jonnin]

a minor side note.. the 3 most common logs in our field are:
lg (base 2)
ln (base e)
log (base 10)

ignoring constants in big-O and general 'jargon/understanding' causes big-o to often have log used where lg is the actual power in question. many, many algorithms are tied to the power of 2 or the idea of cutting in half each iteration, etc. Its fine, but this is not usually explicitly stated as another case of ignoring the constant or well explained and logs are also not well taught anymore.

[Duthomhas]

Yes, optimal make-heap is over a heap requiring no push-downs, leaving n/2 operations.

Once you pull the root node, however, you modify the tree to require put-downs. The sort is then

n n log n

Which is

n log n

Hope this does not confuse OP

[Ganado]

Duthomhas wrote:

n n log n
Which is
n log n

I don't know about OP, but it is confusing me.
Did you mean n + n log n?

[Duthomhas]

Yes, sorry, on phone, bard to type...

[deleted account xyzzy]

on phone, bard to type...

Accidental typo, or deliberate. Either way that was funny as all get-out. :)