Discussion 9: Heapsort

Simple Implementation

Assume you are given access to a class named IntegerBinaryMaxHeap, which models a priority queue using a binary max heap and has the following methods:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17


/** Creates a binary heap in which the items are ordered according to 
  * their values. The heap implements a max-queue: larger values have 
  * higher priorities. */
public IntegerBinaryMaxHeap();

/** Inserts a new item into the queue. Runs in O(log N) time,
 *  where N is the size of this priority queue. */
public void add(int item);

/** Removes and returns the item from the queue with the highest priority.
 *  Requires that the queue contains at least one item. Runs in O(log N)
 *  time, where N is the size of this priority queue. */
public int remove();

/** Returns the number of items stored in this priority queue. 
 *  Runs in O(1) time. */
public int size();

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17


/** Creates a binary heap in which the items are ordered according to 
  * their values. The heap implements a max-queue: larger values have 
  * higher priorities. */
public IntegerBinaryMaxHeap();

/** Inserts a new item into the queue. Runs in O(log N) time,
 *  where N is the size of this priority queue. */
public void add(int item);

/** Removes and returns the item from the queue with the highest priority.
 *  Requires that the queue contains at least one item. Runs in O(log N)
 *  time, where N is the size of this priority queue. */
public int remove();

/** Returns the number of items stored in this priority queue. 
 *  Runs in O(1) time. */
public int size();

Exercise 1: Basic Implementation

(a)

Coding

Using this heap class, write a simple heapsort on an array of integers. Your code should consist of two loops: first to add every element from the array into the heap, and a second to repeatedly poll 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 polled from this heap.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13


/** 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();
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13


/** 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();
  }
}

(b)

Loop Invariants

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).

(c)

Complexity Analysis

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\)?

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.

What is the overall worst-case runtime complexity of your sorting algorithm?

The time complexity is \(O(N \log N)\).

What is its space complexity?

The heap of \(N\) elements uses \(O(N)\) space.

Exercise 2: Smarter Implementation

Since a binary heap is implemented using an array, a clever trick involves building the heap directly in the starting array, allowing heapsort to avoid some unnecessary work. Instead of using the existing heap implementation as a client, you will instead make use of the following helper methods.

1
2
3
4
5
6
7
8


/** Swap elements at index `i` and `j` in the `heap` array. Requires
 *  `0 <= i, j < heap.length`. Runs in O(1) time. */
public static void swap(int[] heap, int i, int j);

/** Repeatedly swaps the element in index `k` in `heap[0..size)` with its 
 *  larger child until it resides at a heap leaf or it is larger than all 
 *  of its children. */
public static void bubbleDown(int[] heap, int k, int size);

1
2
3
4
5
6
7
8


/** Swap elements at index `i` and `j` in the `heap` array. Requires
 *  `0 <= i, j < heap.length`. Runs in O(1) time. */
public static void swap(int[] heap, int i, int j);

/** Repeatedly swaps the element in index `k` in `heap[0..size)` with its 
 *  larger child until it resides at a heap leaf or it is larger than all 
 *  of its children. */
public static void bubbleDown(int[] heap, int k, int size);

(a)

heapify()

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.

Second Hint: Start at the back of the array and move forward. The body of your loop should be a single method call.

1
2
3
4
5
6
7
8


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

1
2
3
4
5
6
7
8


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

We could save a bit more work by starting i halfway through the array instead of the last element, since the second half of the array has nowhere to bubble down. This doesn't change the time complexity of the overall algorithm.

(b)

Efficient Heapsort

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

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.

1
2
3
4
5
6
7
8


/** 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);
  }
}

1
2
3
4
5
6
7
8


/** 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);
  }
}

(c)

Complexity Analysis

We can argue that this heapify() definition has an \(O(N)\) runtime:

We can bound the number total work of heapify() by the total number of swaps that it does during its bubbleDown() calls, as these dominate its runtime.

At most \(\frac{N}{2}\) of the entries will begin at level \(\textrm{height} - 1\) in the tree, and they will require at most one swap when they are bubbled down.

Similarly, at most \(\frac{N}{4}\) of the entries will begin at level \(\textrm{height} - 2\) in the tree, and they will require at most two swap when they are bubbled down.

Continuing this pattern, we find that the total number of swaps can be upper bounded by:

\[ \frac{N}{2} + 2 \cdot \frac{N}{4} + 3 \cdot \frac{N}{8} = N \sum_{i=1}^{\infty} \frac{i}{2^i} = 2N = O(N). \]

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)\).