Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
I'm not sure whether my definition for these 2 terms are correct. Hence, could you help me verify that:
HeapSort: A procedure which sorts an array in place.
Build-Max-Heap: A procedure which runs in linear time, produces a max- heap from an unordered input array.
Is worst-case input = worst-case running time?
If so, given the size n for Build-Max-Heap, would its worst case input be the same as the HeapSort which is $\mathcal{O}(n \log n)$?
HeapSort: A procedure which sorts an array in place.
Can be in-place or not in-place, the point is it's using a heap data structure to help sort.
Building heap is linear with a careful analysis
See more here
