A Common-Sense Guide to Data Structures and Algorithms, Second Edition: Exercise 16.3 Answer page 459

Community PragProg Customers
,
1

@jaywengrow

Like Quicksort, Heapsort is O(N log N). This is because we need to insert N values into the heap, and each insertion takes log N steps.

each insertion takes log N steps.

To avoid ambiguity, it can be improved to either

each pop takes log N steps

OR

each insertion to the sorted array takes log N steps.