Trying to understand max heapify
$Q_1:$ I do not understand the function of max-heapify. It seems like a recursive function, but then somehow it's said to run in logarithmic time because of the height of the tree.


max-heapify can be described as a recursive function. There is no particular prevention from a recursive function running in logarithmic time. For max-heapify, the recurrence is $T(n) \le T(2n/3) + \Theta(1)$ (here $2n/3$ is the worst case when the leaves is exactly half full; where $n$ is the size of the subtree rooted at the node under max-heapify). You can solve it by Master Theorem.

Another way of looking at max-heapify is to unfold the recursions: it "floats down" a value through a path of the subtree, whose length is $\sim \Theta(\lg n)$.


  $Q_2:$ To me this makes no sense, because what if you run max-heapify on a min-heap? It'll have to reverse every single node, which I don't see how this can be done without it touching every single node.


The answer is simple: We don't run max-heapify on a min-heap. Use min-heapify for min-heap instead.