Note that in the tree there is no guarantee that element 4 is lower than element 2, even though it is lower in the table.  For example, element 4 could be 20.0 (still less than its parent 25.5) which is greater than element 2 (15.5), but the required relationships of the tree are still intact.

Here is the fundamental key to the Tree:  If we take any element (call it the ith element), we know that it's parent is as position: (i - 1)/2 (round down).  For example, if i = 8, then its parent is 3; if i = 6, its parent is 2.  Likewise, we know that its children are at positions: (i  * 2) + 1 and (i * 2) + 2. 

We use these rules to reorganize our array.  Suppose we take any value, we can compare it to the values of where its children reside.  If we find that the parent is smaller than either child, we swap the parent for the largest child.  This swap, means that for that node the required parent/child relationship will hold true.

Here is the code to build the Heap:

---------------------------------------------------

let printA (i : int) (rA : float array) =
    printfn "The Heap: %i : %10.1f %10.1f %10.1f %10.1f %10.1f %10.1f %10.1f %10.1f %10.1f %10.1f "
            i rA.[0] rA.[1] rA.[2] rA.[3] rA.[4] rA.[5] rA.[6] rA.[7] rA.[8] rA.[9]

//
// Left Node
//
let left (i : int) =
    i*2 + 1

//
// Right Node
//
let right (i : int) =
    i*2 + 2

//
//Test if Left Node > ith Node
//
let iBig (rA : float array) (iLeft : int) (i : int) (n : int) =
    if iLeft < n then
        if rA.[iLeft] > rA.[i] then
            iLeft
        else
            i
    else
        i

//
//Swap Values
//
let swap (rA : float array) (i : int) (j : int) =
    let x = rA.[i]
    rA.[i] <- rA.[j]
    rA.[j] <- x
    rA

//
//  Recursive function to build the heap
//
let rec BuildTheHeap (rA : float array) (n : int) (i : int) =
    // Recursive loop that works down to zero (including zero)
    match i with
    | -1 -> rA
    | _ -> let rA = heapIt rA i n
           printA i rA
           BuildTheHeap rA  n (i-1)

---------------------------------------------------

So, how does this work?

 The last function 'BuildTheHeap' takes as arguments the array rA, the array length n, and a position in the array i.  In our example, the array length is 10.  The function is initially called at the midpoint of the array (the value 4 in our case).  The function is recursively called, where the position i is decremented until it hit -1.  We do want to include i of zero (0) in our loop.  In effect, this function starts at the midpoint and moves one position to the left at each iteration.

The function 'heapIt' takes a array position i as input and compares it against the values of its two children two children.  What position's do the children hold?   Form above, we know that its children are at positions: (i  * 2) + 1 and (i * 2) + 2.  Hence, we have our two functions 'left' and 'right' that simply return the left and right child nodes of the ith node.  From this, you can see why we start at the midpoint:  any nodes to the right have the midpoint have NO children.

The function iBig compares the ith node to the Left node and returns the relevant index.  Heapit has another function iBigger that tests the right node against iBig and returns the index of the larger value.

Then, we check to see if iBigger not equal to i.  If iBig equals i, it means that the value at i exceeds each of the values of the children, meaning the required relationships for the binary tree hold -- there is nothing to do.  If iBigger does not equal i, it means the value at iBigger is greater than at i.  We need to swap the values in order to reestablish the required binary tree relationship.  This swapping moves the greater value to the left and the lesser value to the right. 

We are not quite done yet.  For example, let's say the value at position 5 is greater than the value at position 2.  We swap the values, thereby demoting 2.  Now, we want to further check to see if the new value at 5 exceeds the values of its children.  If it does, we stop.  But if not, we swap again and reevaluate.  This process continues to the right until we run out of children or the value finds two children with lesser values.

Note:  the printA function just prints the Array to the console.

In agonizing detail, here is how the Heap is built.

This is the initial array:

Position:        0     1     2     3     4     5     6     7     8     9    10
Start:        11.5   8.5   9.5  28.0  25.5  15.0  12.0  11.0   9.0   7.5    <>

The algorithm works on this array (in place) to build the Heap.

Step 1:  Find the midpoint.  Divide the number of elements (less 1) by 2.  We need to subtract 1 because the array is zero based. so that 9 is really the top position not 10.  We then round down. I this value i: 

Step 2:  Starting at the midpoint (position 4), compare the value with the values at a pair of values that are at positions:

left = i + (2*i) + 1
right = i + (2*i) + 2
(positions 9 and 10 in our case)

If the value at position 4 is lower that the value at positions 9 or 10, swap it with the one that is greater.   (In our example position 10 is outside the array boundary, so it is skipped.)   In the example above, 25.5 is greater than 7.5, so we do nothing.

Start:        11.5   8.5   9.5  28.0  25.5  15.0  12.0  11.0   9.0   7.5

We move to the left one position and test the values 28.0 vs 11.0 and 9.0.  Again we have nothing to do.

Start:        11.5   8.5   9.5  28.0  25.5  15.0  12.0  11.0   9.0   7.5

We again move to the left one position and test the values.  Here we have 9.5 versus the pair 15.0 and 12.0.

The Heap:     11.5   8.5  15.0  28.0  25.5   9.5  12.0  11.0   9.0   7.5

We swap 9.5 with 15.0 because it is the larger of the pair.

After we make the swap, we recursively call the heapIt function, starting at the swapped in position (position 5).

Position:     0     1     2     3     4     5     6     7     8     9    10    11
The Heap:  11.5   8.5  15.0  28.0  25.5   9.5  12.0  11.0   9.0   7.5    <>    <>

Here, we compare the value at position 5 versus 10 and 11, both of which are outside the bounds of our array.  So we do nothing. 

So, our first chore, is to take our floating point array of cars MPG's and transform it into a Heap using the rules above.