1
$\begingroup$

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)$?

Improve this question
$\endgroup$
1
  • 1
    $\begingroup$ Famously, building a heap is possible in linear time. $\endgroup$
    – Raphael
    Commented Feb 25, 2015 at 15:21

1 Answer 1

Reset to default
4
$\begingroup$

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

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.