The standard Divide-and-Conquer algorithm usually works as follows:

  1. spend some time handling the base case
  2. if not at the base case, divide the problem up into smaller subproblems: D(n)
  3. make recursive calls to handle all the subproblems created on step 2: T(n/b)
  4. combine results created by recursive calls on step 3: C(n)

利用遞迴分析： 

T(n) = a * T(n/b) + f(n)

  1. a = number of subproblems
  2. n/b = size of the subproblems
  3. f(n) = D(n) + C(n)

以Max-Heapify為例來分析：

  1. a = 1, i.e., there is only one recursive call made
  2. n/b = (2/3) * n, is the worst case size of the one subproblem. The size of the left subtree is (2/3) * n. 也就是說 when the left subtree has one entire full level as compared to the right subtree. The worst case is when the last level of the tree is half full.
  3. f(n) = Q(1), all the work done in lines 1 - 9 above takes a constant time
  4. T(n) = T(2n/3) + Q(1)

Max-Heapify演算法如下:

Max-Heapify(A,i)
1 l ← Left(i)
2 r ← Right(i)
3 if l ≤ heap-size[A] and A[l] > A[i]
4 then largest ← l
5 else largest ← i
6 if r ≤ heap-size[A] and A[r] > A[largest]
7 then largest ← r
8 if largest ≠ i
9 then exchange A[i] ↔ A[largest]
10 Max-Heapify(A, largest)