A proof that Accelerated FixHeap run on an almost-heap of n nodes will perform no more than 
⌊lg n⌋+⌊lg lg n⌋+1
comparisons.

Let (Subscript[C, AccFixHeap])(n) be the number of comparison that the Accelerated FixHeap (call it AFH) performs in the worst case while fixing an almost-heap H on n nodes.

An almost-heap H is very much like a heap except that its root's value may be not large enough to be the root.

AFH will demote the root R of H, if necessary, down along the path P of the larger child. The length of P is no more than ⌊lg n⌋, so AFH will perform no more than 
⌊lg n⌋ 
comparisons (one comp per level) just to find P while demoting R.

This upper bound remains an upper bound even if R has been accidentally demoted too far (say, to the level L, with L comparisons since one comparison is performed for each level) and must be promoted up one or more levels. In such a case, R will be promoted no further then one level below the level at which R was compared most recently to a node in P. The distance (up) of such promotion, measured in the number of levels passed, is not larger than the distance (down) 
⌊lg n⌋-L from L to the last level ⌊lg n⌋of H.(Excercise: Prove it!) Since only one comparison per level is performed while promoting R, the total number of comparisons for all demotions and subsequent promotions (if any) must be not larger than L+ ⌊lg n⌋-L=⌊lg n⌋.

Now comes the Binary Search part.

There are ⌊lg n⌋+1 nodes along P, one of wich is the root R of H. So, there are ⌊lg n⌋remaining nodes along P. All these remaining nodes are ordered decreasingly. AFH needs to find the level of H at which to insert R into P using the Binary Search.

The worst-case number of comparisons performed by Binary Search on m ordered elements is ⌊lg m⌋+1.

Since there are m = ⌊lg n⌋nodes (all nodes of P except for the root R), the worst-case number of comparisons that Binary Search will perform on those nodes is ⌊lg m⌋+1=
⌊lg ⌊lg n⌋⌋+1.

Therefore, the number of comparisons (Subscript[C, AccFixHeap])(n)performed by AFH will be not greater than⌊lg n⌋+⌊lg ⌊lg n⌋⌋+1, that is,

(Subscript[C, AccFixHeap])(n)≤⌊lg n⌋+⌊lg ⌊lg n⌋⌋+1.

Let's simplify ⌊lg ⌊lg n⌋⌋.

⌊lg ⌊lg n⌋⌋=max{i:i≤ lg ⌊lg n⌋}=max{i:(2^i)≤ (2^(lg ⌊lg n⌋))}=max{i:(2^i)≤⌊lg n⌋}.

Now, let's show that for any integer i,
 (2^i)≤⌊lg n⌋⧦(2^i)≤lg n.

Of course, if  (2^i)≤⌊lg n⌋ then (2^i)≤lg n, simply because ⌊lg n⌋≤ lg n.

Let's assume (2^i)≤lg n.

Since i is an integer, (2^i)is an integer, too. Because ⌊lg n⌋is the largest integer m that satisfies m ≤ lg n, we must have (2^i)≤m. In other words, (2^i)≤m=⌊lg n⌋. Hence, (2^i)≤⌊lg n⌋.

This way we proved  (2^i)≤⌊lg n⌋⧦(2^i)≤lg n.

Therefore
max{i:(2^i)≤⌊lg n⌋}=max{i:(2^i)≤lg n}=max{i:lg (2^i)≤lg lg n}=
=max{i:i≤lg lg n} =⌊lg ⌊lg n⌋⌋.

Thus
⌊lg ⌊lg n⌋⌋=⌊lg lg n⌋.

Hence,

(Subscript[C, AccFixHeap])(n)≤⌊lg n⌋+⌊lg lg n⌋+1.

This completes the proof.