heap sort의 시간복잡도는 deleteMax 값을 n번 해줘야해서 O(n*logn)으로 알고있는데


단순히 n개의 input size에 대해 heap construction은 시간복잡도가 O(logn)인가요 아니면 똑같이 O(nlogn)인가요.


n개를 complete binary tree로 만드는데 O(n)시간, 그리고 down-heap을 하는 fixHeap시간 (entity마다 2log(n) time) --> O(log(n)!) =O( n*log(n))

더해서 O( n + n*log(n) ) = O ( n*log(n)) 이게 맞는건가요?


수도코드를 적어보자면


void constructHeap(H)

if(H is not a leaf)

constructHeap (left subtree of H);

constructHeap (right subtree of H);

Element K = root(H);

fixHeap(H,K); // down-heap

return;