Discussion 9 | CS 2110

(a)

Using this heap class, write a simple heapsort on an array of integers. Your code should consist of two loops: the first to add every element from the array into the heap, and the second to repeatedly remove from the heap and re-insert the elements back into the array in sorted order. Remember, the heap provided is a max-heap. Consider what order this means the elements can be removed from this heap.

  package cs2110; 

  import static cs2110.IntegerBinaryMaxHeap.*;

  public class Heapsort {
    // SHOW: SECTION 1
    /** Sorts the given array using a heap. */
    public static void heapsort(int[] arr) {
      // create a max-heap
      IntegerBinaryMaxHeap h = new IntegerBinaryMaxHeap();
      // add all elements from arr into the heap
      for (int i = 0; i < arr.length; i++) {
        h.add(arr[i]);
      }
      // repeatedly remove from heap and reconstruct arr
      for (int i = arr.length - 1; i >= 0; i--) {
        arr[i] = h.remove();
      }
    }
    // SHOW: END 1
  }

(b)

Draw a loop-invariant diagram for the state of the array arr for both of the above loops. Include in your invariant what values are currently inside the heap (but it is not necessary to draw a diagram for the heap itself).

Inv:

arr:

0

arr.length

Inv:

arr:

0

arr.length

(c)

Assuming that the creation of the empty heap can be done in \(O(1)\) time, what is the time complexity of each of your loops relative to the length of the input array \(N\)? What is the overall worst-case runtime complexity of your sorting algorithm? What is its space complexity?

Both loops run in \(O(N \log N)\), as each add() or remove() operation takes \(O(\log N)\) time, and they are done for all \(N\) elements in the array. The time complexity is \(O(N \log N)\). The heap of \(N\) elements uses \(O(N)\) space.

(a)

Start by writing a method that takes an array and rearranges its elements to satisfy the invariants of a max-heap. Hint: Calling bubbleDown() on the root of a subtree will leave the subtree in the correct state as long as all of the children of the subtree's root have already been bubbled down into their correct positions.

  package cs2110; 
  
  import static cs2110.IntegerBinaryMaxHeap.*;

  public class Heapsort {
    // SHOW: SECTION 1
    /** Rearranges the elements in `arr` to fulfill all invariants for a max-heap. */
    public static void heapify(int[] arr) {
      for (int j = arr.length - 1; j >= 0; j--) {
        bubbleDown(arr, j, arr.length);
      }
    }
    // SHOW: END 1
  }

(b)

Now, with the array as a max-heap, loop through the array and "remove" from your heap while building up the sorted region of the array. Use the following invariant for your loop:

Inv:

arr:

0

arr.length

At each iteration, consider what a standard implementation of remove() would do to the element at arr[0]. Recall that this is a max-heap. Where does that element end up? What does the invariant require of that resulting location?

Hint: The body of your loop should make two calls to the helper methods listed above.

  package cs2110; 
  
  import static cs2110.IntegerBinaryMaxHeap.*;

  public class HeapsortEff {
    /** Rearranges the elements in `arr` to fulfill all invariants for a max-heap. */
    public static void heapify(int[] arr) {
      for (int j = arr.length - 1; j >= 0; j--) {
        bubbleDown(arr, j, arr.length);
      }
    }

    // SHOW: SECTION 1
    /** Sorts the given array in-place using a heap. */
    public static void heapsortEff(int[] arr) {
      heapify(arr);
      for (int i = arr.length - 1; i > 0; i--) {
        swap(arr, 0, i);
        bubbleDown(arr, 0, i);
      }
    }
    // SHOW: END 1
  }

(c)

Including the complexity of heapify() you found earlier, what is the total time complexity of your heapsortEff() method? Which of the two steps (heapifying or iterated removing) dominates this complexity?

The time complexity is still \(O(N \log N)\) due to the repeated removes from the heap. This is what dominates the runtime; strangely, the creation of the heap is actually faster than repeatedly removing from it.

What is the space complexity of your heapsortEff() method?

As all work is done in-place in the array, the space complexity is \(O(1)\).

Although the code you've written by this point correctly implements heaps and heapsort, it is much more memorable and conceptually helpful to be able to visualize what heapsort is actually doing, so in this exercise we will trace a full runthrough of the improved heapsort implementation.

Let us suppose that the initial state of the array is:

(a)

During three of the iterations of the main loop of heapify(), the contents of arr are rearrange. Fill in the figures below to visualize the state of arr at the end of these iterations. Label these iterations with the values of any relevant loop variables.

End of iteration: j = 2

End of iteration: j = 1

End of iteration: j = 0

(b)

Draw the binary tree representation of the arr heap at the end of the heapify() method.

(c)

Fill in the state of arr after the first element has been removed from the heap after the heapify() step of heapsortEff(). What value of i does this correspond to in the loop invariant diagram?

This corresponds to the heapsortEff() iteration with i = 5.

(d)

Draw the binary tree representation of the state of the heap segment of arr at the point of the execution of part (c).

(e)

Fill in the state of arr after the first three elements have been removed from the heap after the heapify() step of heapsortEff(). What value of i does this correspond to in the loop invariant diagram?

This corresponds to the heapsortEff() iteration with i = 3.

(f)

Draw the binary tree representation of the state of the heap segment of arr at the point of the execution of part (e).

Discussion 9: Heapsort