The heapsort assignment features the standard sequential implementation of binary trees.

Pseudocode

pseudocode heapsort(a[],n)
   // create initial heap
   for i = floor(n/2) to 1 by -1 do
      adjust(i,n)
   end
   // sort
   for i = n-1 to 1 by -1 do
      t = a[i+1] 
      a[i+1] = a[1]
      a[1] = t
      adjust(1,i)
   end
end

pseudocode adjust(i,n)
   a = a[i]
   j = 2*i
   while ( j <= n ) do
      if ( j < n ) then
         if ( a[j] < a[j+1] ) then
            j = j + 1
         end
      end
      if ( a > a[j] ) then
         exit the loop
      end
      a[j/2] = a[j] 
      j = j*2
   end
   a[j/2] = a
end

Example

1. Initial array elements.

26 5 77 1 61 11 59 15 48 19

2. Draw the binary tree.
3. Create initial heap as a tree.
4. Write sequentially.

77 61 59 48 19 11 26 15 1 5

5. Perform "pass 1" and write sequentially

61 48 59 15 19 11 26 5 1 71

6. Perform "pass 2" and write sequentially

59 48 26 15 19 11 1 5 61 71

7. Continue ...

Questions

1. What is a heap?
2. How do you store a binary tree in a sequential structure?
3. In a heap, how do you reference the parent of the node indexed by i, if it has one?
4. In a heap, how do you reference the left child of the node indexed by i, if it has one?
5. In a heap, how do you reference the right child of the node indexed by i, if it has one?