CSC1020 Homework 12 - Heaps

Visualization

A heap can be thought of as a binary tree, but unlike a Binary Search Tree, a heap is not globally sorted.

Instead, a heap maintains a relationship between every parent and its children:

There is no required ordering between siblings or between nodes in different branches of the tree.

A heap is also always a Complete Tree. Each level is filled from left to right before a new level is started.

Adding to a Heap

When adding a new element to the Heap, place it in the next available position in the complete tree. Because the heap is backed by an ArrayList, this means adding the new element to the end of the list.

After insertion, the element may violate the heap-order property. It must therefore bubble up toward the root.

Compare the new element with its parent. If the new element has higher priority than its parent, swap the two elements. Continue until either:

The meaning of "higher priority" is determined by the compare(E a, E b) method described below. This allows the same heap algorithm to work for both MinHeap and MaxHeap.

Removing from a Heap

Elements are removed from the top of the Heap using the poll() method.

When the root is removed:

  1. Save the root value so it can be returned.
  2. Move the final element in the backing ArrayList to the root.
  3. Repeatedly compare that element with its children.
  4. If both children exist, determine which child has higher priority.
  5. If the higher-priority child also has higher priority than the current element, swap them and continue.
  6. Stop when the element has priority over its children or when it has no children.

If the heap is empty, poll() returns null.

Implementation of a Heap

A Heap is often implemented as an array- or list-backed priority queue. Although its behavior can be visualized as a binary tree, the parent/child relationships are represented using indexes in the backing structure.

For this assignment, you will implement the following hierarchy:

HW12UML.png

Heap Interface

Create the interface:

public interface Heap<E extends Comparable<? super E>>

The Heap interface must define these methods:

AbstractHeap

Create the abstract class:

public abstract class AbstractHeap<E extends Comparable<? super E>>
        implements Heap<E>

AbstractHeap must use an ArrayList<E> as its backing structure and contain the following fields:

private static final int INITIAL_CAPACITY = 10;
private final ArrayList<E> data;

The no-argument constructor initializes data using INITIAL_CAPACITY.

The class must implement:

It must also define:

protected abstract int compare(E a, E b);

The compare() method defines which of two elements has higher heap priority:

AbstractHeap must also contain this private helper:

private void swap(int a, int b)

which swaps the two elements in data at indexes a and b.

ArrayList Representation

When elements are stored in the heap, they are placed in the ArrayList in complete-tree order.

For an element at index i:

parent      = (i - 1) / 2
left child  = 2 * i + 1
right child = 2 * i + 2

These relationships are what allow the heap to behave like a binary tree without storing explicit node objects.

For example, suppose the backing ArrayList stores:

A B C D E F G H

The root node is A at index 0. The left child of A is B and the right child is C.

The parent of C, at index 2, is:

(2 - 1) / 2 = 0

so A is its parent.

The parent of H, at index 7, is:

(7 - 1) / 2 = 3

so D is its parent.

The tree representation is:

HW12Tree.png

MinHeap and MaxHeap

Create these two concrete subclasses:

public class MaxHeap<E extends Comparable<? super E>>
        extends AbstractHeap<E>
public class MinHeap<E extends Comparable<? super E>>
        extends AbstractHeap<E>

Each class implements the inherited compare(E a, E b) method to define priority.

For a MaxHeap, the element with the larger natural-order value has higher priority. As a result, poll() returns elements from largest to smallest.

For a MinHeap, the element with the smaller natural-order value has higher priority. As a result, poll() returns elements from smallest to largest.

The bubbling algorithms in AbstractHeap must depend on compare() rather than directly assuming that larger or smaller values have higher priority.