(Assuming no duplicate key values:) The order of the input records has what impact on the number of comparisons required by Heapsort (as presented in this module)?

There is a constant factor difference
  • None
  • There is a big difference, the asymptotic running time can change

Can Heapsort's behavior change depending on outcome of a comparison?

Yes, it changes things a little bit in that it might move things up and down the heap more or less.

But this does not matter, because removing a value from the heap normally costs \log n.