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

$\endgroup$
  • 1
    $\begingroup$ Famously, building a heap is possible in linear time. $\endgroup$ – Raphael Feb 25 '15 at 15:21
2
$\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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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