Each reheapUpMax step moves a value at most log2(n) places. There are n−1 reheapUpMax steps to do, so the total time is O(nlog2(n)).
We have overcounted, since not all of the values can move all the way up the tree. For example, values that are chilren of the root can only move one place before they reach the root. But the overcounting is not as bad as it looks. At least half of the values are in the bottom level or next-to-bottom level. Those values can move all the way up the tree. So the total time, in the worst case, is also Ω(nlog2(n)).